COMMENT ⊗   VALID 00017 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	\input acphdr % Section 4.6
C00004 00003	%folio 515 galley 14 Bad spots. (C) Addison-Wesley 1978	*
C00015 00004	%folio 518 galley 1 (C) Addison-Wesley 1978	*
C00027 00005	%folio 520 galley 2 (C) Addison-Wesley 1978	*
C00038 00006	%folio 522 galley 3 (C) Addison-Wesley 1978	*
C00049 00007	%folio 524 galley 4 (C) Addison-Wesley 1978	*
C00059 00008	%folio 526 galley 5 (C) Addison-Wesley 1978	*
C00073 00009	%folio 528 galley 6 Beginning lost. (C) Addison-Wesley 1978	*
C00085 00010	%folio 530 galley 7 (C) Addison-Wesley 1978	*
C00101 00011	%folio 535 galley 8 (C) Addison-Wesley 1978	*
C00120 00012	%folio 539 galley 9 Almost total loss. (C) Addison-Wesley 1978	*
C00128 00013	%folio 541 galley 10 (C) Addison-Wesley 1978	*
C00139 00014	%folio 543 galley 11 (C) Addison-Wesley 1978	*
C00150 00015	%folio 545 galley 12 (C) Addison-Wesley 1978	*
C00166 00016	%folio 550 galley 13 (C) Addison-Wesley 1978	*
C00186 00017	%folio 558 galley 14 (C) Addison-Wesley 1978	*
C00205 ENDMK
C⊗;
\input acphdr % Section 4.6
\runninglefthead{ARITHMETIC} % chapter title
\titlepage\setcount00
\null
\vfill
\tenpoint
\ctrline{SECTION 4.6 of THE ART OF COMPUTER PROGRAMMING}
\ctrline{$\copyright$ 1978 Addison--Wesley Publishing Company, Inc.}
\vfill
\runningrighthead{POLYNOMIAL ARITHMETIC}
\section{4.6}
\eject
\setcount0 387
%folio 515 galley 14 Bad spots. (C) Addison-Wesley 1978	*
\def\\#1({\mathop{\hjust{#1}}(}
\sectionbegin{4.6. POLYNOMIAL ARITHMETIC}
T{\:cHE TECHNIQUES} we have been studying apply in a natural way to many different
types of mathematical quantities, not simply to numbers.
In this section we shall deal with polynomials, which are the next step up
from numbers. Formally speaking, a
{\sl polynomial over} $S$ is an expression of the form
$$u(x) = u↓nx↑n + \cdots + u↓1x + u↓0,\eqno (1)$$
where the ``coefficients'' $u↓n$, $\ldotss$, $u↓1$,
$u↓0$ are elements of some algebraic system $S$, and the ``variable''
$x$ may be regarded as a formal symbol with an indeterminate
meaning. We will assume that the algebraic system $S$ is a {\sl
commutative ring with identity\/}; this means that $S$ admits
the operations of addition, subtraction, and multiplication,
satisfying the customary properties: Addition and multiplication
are associative and commutative binary operations defined on
$S$, where multiplication distributes over addition; and subtraction
is the inverse of addition. There is an additive identity element
0 such that $a + 0 = a$, and a multiplicative identity element
1 such that $a \cdot 1 = a$, for all $a$ in $S$. The polynomial
$0x↑{n+m} + \cdots + 0x↑{n+1} + u↓nx↑n + \cdots + u↓1x + u↓0$
is regarded as the same polynomial as (1), although its expression
is formally different.

We say that (1) is a polynomial of {\sl degree} $n$ and {\sl leading
coefficient} $u↓n$ if $u↓n ≠ 0$; and in this case we write
$$\\deg(u) = n,\qquad \lscr(u) = u↓n.\eqno (2)$$
By convention, we also set
$$\\deg(0) = -∞,\qquad \lscr(0) = 0,\eqno (3)$$
where ``0'' denotes the zero polynomial whose coefficients
are all zero. We say $u(x)$ is a {\sl monic polynomial\/} if $\lscr(u)
= 1$.

Arithmetic on polynomials consists primarily of addition, subtraction,
and multiplication; in some cases, further operations such as division,
exponentiation, factoring, and taking the greatest common divisor are important. 
The processes of addition, subtraction, and multiplication are defined in
a natural way, as though the variable $x$ were an element of
$S$: Addition and subtraction are done by adding or subtracting
the coefficients of like powers of $x$. Multiplication is done
by the rule
$$(u↓rx↑r + \cdots + u↓0)(v↓sx↑s +\cdots+ v↓0)
= (w↓{r+s}x↑{r+s} + \cdots + w↓0),$$
where
$$w↓k = u↓0v↓k + u↓1v↓{k-1} + \cdots + u↓{k-1}v↓1 + u↓kv↓0.\eqno(4)$$
In the latter formula $u↓i$ or $v↓j$ are treated
as zero if $i>r$ or $j > s$.

The algebraic system $S$ is usually the
set of integers, or the rational numbers; or it may itself be
a set of polynomials (in variables other than $x$); in the latter
situation (1) is a {\sl multivariate} polynomial, a polynomial
in several variables. Another important case occurs when the
algebraic system $S$ consists of the integers 0, 1, $\ldotss$,
$m - 1$, with addition, subtraction, and multiplication performed
mod $m$ (cf.\ Eq.\ 4.3.2--11); this is called {\sl polynomial
arithmetic modulo $m$.} The special case of polynomial arithmetic modulo
2, when each of the coefficients
is 0 or 1, is especially important.

The reader should note the similarity between polynomial arithmetic
and multiple-precision arithmetic (Section 4.3.1), where the
radix $b$ is substituted for\penalty999\ $x$. The chief difference is that
the coefficient $u↓k$ of $x↑k$ in polynomial arithmetic bears
little or no essential relation to its neighboring coefficients
$u↓{k\pm1}$, so the idea of ``carrying'' from one place to the
next is absent. In fact, polynomial arithmetic modulo $b$ is
essentially identical to multiple-precision arithmetic with
radix $b$, except that all carries are suppressed. For example,
compare the multiplication of $(1101)↓2$ by $(1011)↓2$ in the binary
number system with the analogous multiplication of $x↑3 + x↑2
+ 1$ by $x↑3 + x + 1$ modulo 2:
$$\def\\{\lower2.323pt\vjust to 12pt{}}\baselineskip0pt\lineskip0pt
\vjust{\halign{\hfill#⊗#\hfill\hskip100pt⊗\hfill#⊗#\hfill\cr
\\Binary syst⊗em⊗Polynomials m⊗odulo 2\cr
\noalign{\vskip2pt}
\\1101⊗⊗1101\cr
$\underline{\\\times1011}$⊗⊗$\underline{\\\times1011}$\cr
\\1101⊗⊗1101\cr
\\1101\9⊗⊗1101\9\cr
$\underline{\\1101\9\9\9}$⊗⊗$\underline{\\1101\9\9\9}$\cr
\\10001111⊗⊗1111111\cr}}$$
The product of these polynomials modulo 2 is obtained
by suppressing all carries, and it is $x↑6 + x↑5 + x↑4 + x↑3
+ x↑2 + x + 1$. If we had multiplied the same polynomials over
the integers, without taking residues modulo 2, the result would
have been $x↑6 + x↑5 + x↑4 + 3x↑3 + x↑2 + x + 1$; again carries
are suppressed, but in this case the coefficients can get arbitrarily
large.

In view of this strong analogy with multiple-precision arithmetic,
it is unnecessary to discuss polynomial addition, subtraction,
and multiplication much further in this section. However, we
should point out some factors that often make polynomial arithmetic
somewhat different from multiple-precision arithmetic in practice:
There is often a tendency to have a large number of zero coefficients,
and polynomials of huge degrees, so special forms of representation
are desirable; this situation is considered in Section 2.2.4.
Furthermore, arithmetic on polynomials in several variables
leads to routines that are best understood in a recursive framework;
this situation is discussed in Chapter 8.

Although the techniques
of polynomial addition, subtraction, and multiplication are
comparatively straightforward, there are several other important
aspects of polynomial arithmetic that deserve special examination.
The following subsections therefore discuss {\sl division} of
polynomials, with associated techniques such as finding greatest
common divisors and factoring. We shall also discuss the problem of efficient
{\sl evaluation} of polynomials, i.e., the task of finding the value of
$u(x)$ when $x$ is a given element of $S$, using as few operations
as possible. The special case of evaluating $x↑n$ rapidly
when $n$ is large is quite important by itself, so it is discussed in
detail in Section 4.6.3.

The first major set of computer subroutines for doing polynomial
arithmetic was the ALPAK system [W. S. Brown, J. P. Hyde, and
B. A. Tague, {\sl Bell System Tech.\ J.} {\bf 42} (1963),
2081--2119; {\bf 43} (1964), 785--804, 1547--1562]. Another
early landmark in this field was the PM system of George Collins [{\sl CACM
\bf9} (1966), 578--589]; see also C. L. Hamblin, {\sl Comp.\ J.
\bf10} (1967), 168--171.
%folio 518 galley 1 (C) Addison-Wesley 1978	*
\def\\#1({\mathop{\hjust{#1}}(}
\exbegin{EXERCISES}

\exno 1. [10] If we are
doing polynomial arithmetic modulo 10, what is $7x + 2$ minus
$x↑2 + 3$? What is $6x↑2 + x + 3$ times $5x↑2 + 2?$

\exno 2. [17] True or false:\xskip (a) The product of monic polynomials
is monic.\xskip (b) The product of polynomials of respective degrees
$m$ and $n$ has degree $m + n$.\xskip (c) The sum of polynomials of respective
degrees $m$ and $n$ has degree $\max(m,n)$.

\exno 3. [M20] If each of the coefficients $u↓r$, $\ldotss$, $u↓0$,
$v↓s$, $\ldotss$, $v↓0$ in (4) is an integer satisfying the conditions
$|u↓i| ≤ m↓1$, $|v↓j| ≤ m↓2$, what is the maximum absolute value
of the product coefficients $w↓k$?

\trexno 4. [21] Can the multiplication of polynomials modulo 2
be facilitated by using the ordinary arithmetic operations on
a binary computer, if coefficients are packed into computer
words?

\trexno 5. [M21] Show how to multiply
two polynomials of degree $≤n$, modulo 2, with an execution
time proportional to $O(n↑{\lg3})$ when $n$ is large, by adapting
Karatsuba's method (cf.\ Section 4.3.3).

\runningrighthead{DIVISION OF POLYNOMIALS}
\section{4.6.1}
\sectionskip
\sectionbegin{4.6.1. Division of Polynomials}
It is possible to divide one polynomial by another
in essentially the same way that we divide one multiple-precision
integer by another, when arithmetic is being done on polynomials
over a ``field.'' A field $S$ is a commutative ring with identity,
in which exact division is possible as well as the operations
of addition, subtraction, and multiplication; this means as
usual that whenever $u$ and $v$ are elements of\penalty999\ $S$ and $v ≠
0$, there is an element $w$ in $S$ such that $u = vw$. The most
important fields of coefficients that arise in applications
are

\yskip\hang\textindent{a)}the rational numbers (represented as fractions,
see Section 4.5.1);

\hang\textindent{b)}the real or complex numbers (represented within a
computer by means of floating-point approximations; see Section
4.2);

\hang\textindent{c)}the integers modulo $p$ where $p$ is prime (with division
implemented as suggested in exercise 4.5.2--15);

\hang\textindent{d)}``rational functions'' over a field (namely, quotients
of two polynomials whose coefficients are in that field, the
denominator being monic).

\yskip\noindent Of special importance is the field
of integers modulo 2, when the two values 0 and 1 are the only
elements of the field. Polynomials over this field (namely polynomials
modulo 2) have many analogies to integers expressed in binary
notation; and rational functions over this field have striking
analogies to rational numbers whose numerator and denominator
are represented in binary notation.

Given two polynomials $u(x)$ and $v(x)$ over a
field, with $v(x) ≠ 0$, we can divide $u(x)$ by $v(x)$ to obtain
a quotient polynomial $q(x)$ and a remainder polynomial $r(x)$
satisfying the conditions
$$u(x) = q(x) \cdot v(x) + r(x),\qquad\\deg(r) <\\deg(v).\eqno(1)$$
It is easy to see that there is at most one pair of polynomials
$\biglp q(x), r(x)\bigrp$ satisfying these relations;
for if (1) holds for both $\biglp q↓1(x), r↓1(x)\bigrp$
and $\biglp q↓2(x), r↓2(x)\bigrp$ and for the same
polynomials $u(x), v(x)$, then $q↓1(x)v(x) + r↓1(x) = q↓2(x)v(x)
+ r↓2(x)$, so $\biglp q↓1(x) - q↓2(x)\bigrp v(x) = r↓2(x) -
r↓1(x)$. Now if $q↓1(x) - q↓2(x)$ is nonzero, then deg$\biglp
(q↓1 - q↓2) \cdot v\bigrp =\\deg(q↓1 - q↓2) +
\\deg(v) ≥\\deg(v) >\\deg(r↓2 - r↓1)$, a contradiction; hence
$q↓1(x) - q↓2(x) = 0$ and $r↓1(x) = 0$.

The following algorithm, which is essentially the
same as Algorithm 4.3.1D for multiple-precision division but
without any concerns of carries, may be used to determine $q(x)$
and $r(x)$:

\algbegin Algorithm D. (Division of polynomials over
a field). Given polynomials
$$u(x) = u↓mx↑m +\cdots + u↓1x + u↓0,\qquad v(x)
= v↓nx↑n +\cdots + v↓1x + v↓0$$
over a field $S$, where $v↓n ≠ 0$ and $m ≥ n ≥
0$, this algorithm finds the polynomials
$$q(x) = q↓{m-n}x↑{m-n} +\cdots + q↓0,\qquad r(x)
= r↓{n-1}x↑{n-1} +\cdots + r↓0$$
over $S$ that satisfy (1).

\algstep D1. [Iterate on $k$.]
Do step D2 for $k = m - n$, $m - n - 1$, $\ldotss$, 0; then the
algorithm terminates with $(r↓{n-1}, \ldotss , r↓0) ← (u↓{n-1},
\ldotss , u↓0)$.

\algstep D2. [Division loop.] Set $q↓k ← u↓{n+k}/v↓n$,
and then set $u↓j ← u↓j - q↓kv↓{j-k}$ for $j = n + k - 1$, $n
+ k - 2$, $\ldotss$, $k$.\xskip (The latter operation amounts to replacing
$u(x)$ by $u(x) - q↓kx↑kv(x)$, a polynomial of degree $<n +
k$.)\quad\blackslug

\yyskip An example of Algorithm D
appears below in (5). The number of arithmetic operations is
essentially proportional to $n(m - n + 1)$. For some reason
this procedure has become known as ``synthetic division'' of
polynomials. Note that explicit division of coefficients is
done only at the beginning of step D2, and the divisor
is always $v↓n$; thus if $v(x)$ is a monic polynomial (with $v↓n
= 1$), there is no actual division at all. If multiplication
is easier to perform than division it will be preferable to
compute $1/v↓n$ at the beginning of the algorithm and to multiply
by this quantity in step D2.

We shall occasionally write $u(x)\mod v(x)$ for
the remainder $r(x)$ in (1).

\subsectionbegin{Unique factorization domains} If
we restrict consideration to polynomials over a field, we are
not coming to grips with many important cases, such as polynomials
over the integers or polynomials in several variables. Let
us therefore now consider the more general situation that the
algebraic system $S$ of coefficients is a {\sl unique factorization domain},
not necessarily a field. This means that $S$ is a commutative
ring with identity, and that

\yskip\hang\textindent{i)}$uv ≠ 0$, whenever $u$ and $v$ are nonzero elements
of $S$;

\hang\textindent{ii)}every nonzero element $u$ of $S$ is either a ``unit''
or has a ``unique'' representation of the form
$$u = p↓1 \ldotsm p↓t,\qquad t ≥ 1,\eqno (2)$$
where $p↓1$, $\ldotss$, $p↓t$ are ``primes.''

\yskip\noindent Here a ``unit'' $u$ is an element that has a reciprocal, i.e.,
an element such that $uv = 1$
for some $v$ in $S$; and a ``prime'' $p$ is a nonunit element
such that the equation $p = qr$ can be true only if either $q$
or $r$ is a unit. The representation (2) is to be unique in
the sense that if $p↓1 \ldotsm p↓t = q↓1 \ldotsm q↓s$, where all
the $p$'s and $q$'s are primes, then $s = t$ and there is a
permutation $π↓1\ldotsm π↓t$ such that $p↓1 = a↓1q↓{π↓1}$,
$\ldotss$, $p↓t = a↓tq↓{π↓t}$ for some units $a↓1$, $\ldotss
$, $a↓t$. In other words, factorization into primes is unique,
except for unit multiples and except for the order of the factors.

Any field is a unique factorization domain, in
which each nonzero element is a unit and there are no primes.
The integers form a unique factorization domain in which the
units are $+1$ and $-1$, and the primes are $\pm 2$, $\pm 3$, $\pm 5$,
$\pm 7$, $\pm11$, etc. The case that $S$ is the set of all integers is
of principal importance, because it is often preferable to work
with integer coefficients instead of arbitrary rational coefficients.
%folio 520 galley 2 (C) Addison-Wesley 1978	*
\def\\#1({\mathop{\hjust{#1}}(}
\def\+#1\biglp{\mathop{\hjust{#1}}\biglp}
One of the key facts about polynomials (see exercise 10) is that
{\sl the polynomials over a unique factorization domain form
a unique factorization domain.} A\penalty999\ polynomial that is ``prime''
in this domain is usually called an {\sl irreducible polynomial.}
By using the unique factorization theorem repeatedly, we can
prove that multivariate polynomials over the integers, or over
any field, in any number of variables, can be uniquely factored
into irreducible polynomials. For example, the multivariate
polynomial $90x↑3 - 120x↑2y + 18x↑2yz - 24xy↑2z$ over the integers
is the product of five irreducible polynomials $2 \cdot 3 \cdot
x \cdot (3x - 4y) \cdot (5x + yz)$. The same polynomial, as
a polynomial over the rationals, is the product of three irreducible
polynomials $(6x) \cdot (3x - 4y) \cdot (5x + yz)$; this factorization
can also be written $x \cdot (90x - 120y) \cdot (x + {1\over
5}yz)$ and in infinitely many other ways, although the factorization
is essentially unique.

As usual, we say that $u(x)$ is a multiple of $v(x)$,
and $v(x)$ is a divisor of $u(x)$, if $u(x) = v(x)q(x)$ for
some polynomial $q(x)$. If we have an algorithm to tell whether
or not $u$ is a multiple of $v$ for arbitrary elements $u$ and
$v ≠ 0$ of a unique factorization domain $S$, and to determine
$w$ if $u = v \cdot w$, then Algorithm\penalty999\ D gives us a method to
tell whether or not $u(x)$ is a multiple of $v(x)$ for arbitrary polynomials $u(x)$
and $v(x) ≠ 0$ over $S$. For if $u(x)$ is a multiple of $v(x)$,
it is easy to see that $u↓{n+k}$ must be a multiple of $v↓n$
each time we get to step D2, hence the quotient $u(x)/v(x)$ will
be found.\xskip (Applying this observation repeatedly, we obtain an
algorithm that decides if a given polynomial over $S$, in any number of variables,
is a multiple of another given polynomial over $S$, and the algorithm will find
the quotient when it exists.)

A set of elements of a unique factorization domain is said to
be {\sl relatively prime} if no prime of that unique factorization
domain divides all of them. A polynomial over a unique factorization
domain is called {\sl primitive} if its coefficients are relatively
prime.\xskip (This concept should not be confused with the quite different
idea of ``primitive polynomials modulo $p$'' discussed in Section
3.2.2.)\xskip The following fact is of prime importance:

\algbegin Lemma G (\rm Gauss's Lemma). {\sl The product of
primitive polynomials over a unique factorization domain is
primitive.}

\proofbegin Let $u(x) = u↓mx↑m +\cdots+
u↓0$ and $v(x) = v↓nx↑n +\cdots + v↓0$ be primitive
polynomials. If $p$ is any prime of the domain, we must show
that $p$ does not divide all the coefficients of $u(x)v(x)$.
By assumption, there is an index $j$ such that $u↓j$ is not
divisible by $p$, and an index $k$ such that $v↓k$ is not divisible
by $p$. Let $j$ and $k$ be as small as possible; then the coefficient
of $x↑{j+k}$ in $u(x)v(x)$ is $u↓jv↓k + u↓{j+1}v↓{k-1} +
\cdots + u↓{j+k}v↓0 + u↓{j-1}v↓{k+1} +\cdots
+ u↓0v↓{k+j}$, and this is not a multiple of $p$ (since its
first term isn't, but all of its other terms are).\quad\blackslug

\yyskip If a nonzero polynomial $u(x)$ over $S$
is not primitive, we can write $u(x) = p↓1 \cdot u↓1(x)$, where
$p↓1$ is a prime of $S$ dividing all the coefficients of $u(x)$,
and where $u↓1(x)$ is another nonzero polynomial over $S$. All
of the coefficients of $u↓1(x)$ have one less prime factor than
the corresponding coefficients of $u(x)$. Now if $u↓1(x)$ is
not primitive, we can write $u↓1(x) = p↓2 \cdot u↓2(x)$, etc.,
and this process must ultimately terminate in a representation
$u(x) = c \cdot u↓k(x)$, where $c$ is an element of $S$ and
$u↓k(x)$ is primitive. In fact, we have the following lemma:

\thbegin Lemma H. {\sl Any nonzero polynomial $u(x)$ over
a unique factorization domain $S$ can be factored in the form
$u(x) = c \cdot v(x)$, where $c$ is in $S$ and $v(x)$ is primitive.
Furthermore, this representation is unique, in the sense that
if $u = c↓1 \cdot v↓1(x) = c↓2 \cdot v↓2(x)$, then $c↓1 = ac↓2$
and $v↓2(x) = av↓1(x)$ where $a$ is a unit of $S$.}

\proofbegin We have shown that such a representation
exists, and so only the uniqueness needs to be proved. Assume
that $c↓1 \cdot v↓1(x) = c↓2 \cdot v↓2(x)$, where $v↓1(x)$ and
$v↓2(x)$ are primitive and $c↓1$ is not a unit multiple of $c↓2$.
By unique factorization there is a prime $p$ of $S$ and an exponent
$k$ such that $p↑k$ divides one of $\{c↓1, c↓2\}$ but not the
other, say $p↑k$ divides $c↓1$ but not $c↓2$. Then $p↑k$ divides
all of the coefficients of $c↓2 \cdot v↓2(x)$, so $p$ divides
all the coefficients of $v↓2(x)$, contradicting the assumption
that $v↓2(x)$ is primitive. Hence $c↓1 = ac↓2$, where $a$ is
a unit; and $0 = ac↓2 \cdot v↓1(x) - c↓2 \cdot v↓2(x) = c↓2
\cdot \biglp av↓1(x) - v↓2(x)\bigrp$ implies that $av↓1(x)
- v↓2(x) = 0$.\quad\blackslug

\yyskip Therefore we may write any nonzero polynomial
$u(x)$ as
$$u(x) =\\cont(u) \cdot\+pp\biglp u(x)\bigrp ,\eqno (3)$$
where cont$(u)$, the ``content'' of $u$,
is an element of $S$, and pp$\biglp u(x)\bigrp $,
the ``primitive part'' of $u(x)$, is a primitive polynomial
over $S$. When $u(x) = 0$, it is convenient to define $\\cont(u)
=\+pp\biglp u(x)\bigrp= 0$. Combining Lemmas G
and H gives us the relations
$$\eqalign{\\cont(u \cdot v) ⊗= a\\cont(u)\\cont(v),\cr
\+pp\biglp u(x) \cdot v(x)\bigrp ⊗ = b\+pp\biglp
u(x)\bigrp\+pp\biglp v(x)\bigrp ,\cr}\eqno (4)$$
where $a$ and $b$ are units, depending on $u$ and $v$,
with $ab = 1$. When we are working with polynomials over the
integers, the only units are $+1$ and $-1$, and it is conventional
to define pp$\biglp u(x)\bigrp$ so that its leading
coefficient is positive; then (4) is true with $a = b = 1$.
When working with polynomials over a field we may take cont$(u)
=\lscr(u)$, so that pp$\biglp u(x)\bigrp$ is monic;
in this case again (4) holds with $a = b = 1$, for all $u(x)$
and $v(x)$.

For example, if we are dealing with polynomials
over the integers, let $u(x) = -26x↑2 + 39$ and $v(x) = 21x + 14$.
Then
$$\baselineskip15pt
\eqalign{\\cont(u)⊗=-13,\cr \\cont(v)⊗=+7,\cr \\cont(u\cdot v)⊗=-91\cr}\qquad\qquad
\eqalign{\+pp\biglp u(x)\bigrp⊗=2x↑2-3,\cr
\+pp\biglp v(x)\bigrp⊗=3x+2,\cr
\+pp\biglp u(x)\cdot v(x)\bigrp⊗=6x↑3+4x↑2-9x-6.\cr}$$
%folio 522 galley 3 (C) Addison-Wesley 1978	*
\def\\#1({\mathop{\hjust{#1}}(}\def\+#1\biglp{\mathop{\hjust{#1}}\biglp}
\subsectionbegin{Greatest common divisors} When there
is unique factorization, it makes sense to speak of a ``greatest
common divisor'' of two elements; this is a common divisor that
is divisible by as many primes as possible.\xskip (Cf.\ Eq.\ 4.5.2--6.)\xskip
Since a unique factorization domain may have many units, there
is a certain amount of ambiguity in this definition of greatest
common divisor; if $w$ is a greatest common divisor of $u$ and
$v$, so is $a \cdot w$, when $a$ is a unit. Conversely, the
assumption of unique factorization implies that if $w↓1$ and
$w↓2$ are both greatest common advisors of $u$ and $v$, then
$w↓1 = a \cdot w↓2$ for some unit $a$. Therefore it does not
make sense, in general, to speak of ``the'' greatest common
divisor of $u$ and $v$; there is a set of greatest common divisors,
each one being a unit multiple of the others.

Let us now consider the problem of finding a greatest
common divisor of two given polynomials over an algebraic system
$S$. If $S$ is a field, the problem is relatively simple; our
division algorithm, Algorithm D\null, can be extended to an algorithm
that computes greatest common divisors, just as Euclid's algorithm
(Algorithm 4.5.2A) yields the greatest common divisor of two
given integers based on a division algorithm for integers: If
$v(x) = 0$, then gcd$\biglp u(x), v(x)\bigrp = u(x)$; otherwise
$\gcd\biglp u(x), v(x)\bigrp = \gcd\biglp v(x), r(x)\bigrp
$, where $r(x)$ is given by (1). This procedure is called Euclid's algorithm
for polynomials over a field; it was first used by Simon Stevin
in 1585 [{\sl Les \oe uvres math\'ematiques de Simon Stevin},
ed.\ by A. Girard, {\bf 1} (Leyden, 1634), 56].

For example, let us determine the gcd of $x↑8 +
x↑6 + 10x↑4 + 10x↑3 + 8x↑2 + 2x + 8$ and $3x↑6 + 5x↑4 + 9x↑2
+ 4x + 8$, mod 13, by using Euclid's algorithm for polynomials
over the integers modulo 13. First, writing only the coefficients
to show the steps of Algorithm D\null, we have
$$\def\\{\lower2.323pt\vjust to 12pt{}}\baselineskip0pt\lineskip0pt
\vcenter{\halign{$\hfill#$\cr
\lower2.732pt\vjust to 12pt{}9\90\97\cr
\\3\90\95\90\99\94\98\9\overline{\vcenter{\vskip-.818pt
\hjust{\raise1pt\hjust{$\bigrp$}\91\90\91\90\910\910\9\98\92\98}\vskip.182pt}}\cr
\underline{\\1\90\96\90\9\93\910\9\97\9\9\9\9}\cr
\\0\98\90\9\97\9\90\9\91\92\98\cr
\underline{\\8\90\9\99\9\90\911\92\94}\cr
\\0\911\9\90\9\93\90\94\cr}}\eqno (5)$$
and hence
$$\twoline{x↑8 + x↑6 + 10x↑4 + 10x↑3 + 8x↑2 + 2x + 8}{2pt}{=
(9x↑2 + 7)(3x↑6 + 5x↑4 + 9x↑2 + 4x + 8)\;+\;(11x↑4
+ 3x↑2 + 4).}$$
Similarly,
$$\baselineskip15pt\vjust{\tabskip 0pt plus 1000pt minus 1000pt
   \halign to size{\hfill$\dispstyle{#}$\tabskip 0pt⊗$ #$\hfill
   ⊗$\dispstyle{\null#}$\hfill\tabskip 0 pt plus 1000pt minus 1000pt
   ⊗\hfill$ #$\tabskip 0pt\cr
3x↑6 + 5x↑4  + 9x↑2 + 4⊗x + 8 ⊗= (5x↑2
+ 5)(11x↑4 + 3x↑2 + 4)\; +\; (4x + 1);\cr
11x↑4 + 3x↑2 +4⊗
⊗= (6x↑3 + 5x↑2 + 6x + 5)(4x + 1)\;+\;12;\cr
4⊗x + 1 ⊗= (9x + 12) \cdot 12\;+\;0.⊗(6)\cr}}$$
(The equality sign here means congruence modulo 13,
since all arithmetic on the coefficients has been done mod 13.)\xskip
This computation shows that 12 is a greatest common divisor
of the two original polynomials. Now any nonzero element of
a field is a unit of the domain of polynomials over that field,
so any nonzero multiple of a greatest common divisor is also
a greatest common divisor (over a field). It is therefore conventional
in this case to divide the result of the algorithm by its leading
coefficient, producing a {\sl monic} polynomial that is called
{\sl the} greatest common advisor of the two given polynomials.
The gcd computed in (6) is accordingly taken to be 1, not 12.
The last step in (6) could have been omitted, for if deg$(v)
= 0$, then gcd$\biglp u(x), v(x)\bigrp = 1$, no matter what
polynomial is chosen for $u(x)$. Exercise 4 determines the average
running time for Euclid's algorithm on random polynomials modulo
$p$.

Let us now turn to the more general situation
in which our polynomials are given over a unique factorization
domain that is not a field. From Eqs.\ (4) we can deduce the
important relations
$$\baselineskip15pt\eqalign{\+cont\biglp\gcd(u,v)\bigrp ⊗= a \cdot\gcd\biglp
\\cont(u),\\cont(v)\bigrp ,\cr
\+pp\biglp\gcd(u(x), v(x))\bigrp ⊗= b \cdot\gcd\biglp
\+pp\biglp u(x)\bigrp, pp\biglp v(x)\bigrp\bigrp,\cr}\eqno (7)$$
where $a$ and $b$ are units. Here $\gcd\biglp u(x), v(x)\bigrp$
denotes any particular polynomial in $x$ that is a greatest
common divisor of $u(x)$ and $v(x)$. Equations (7) reduce the
problem of finding greatest common divisors of arbitrary polynomials
to the problem of finding greatest common divisors of {\sl primitive}
polynomials.

Algorithm D for division of polynomials over a
field can be generalized to a pseudo-division of polynomials
over any algebraic system that is a commutative ring with identity.
We can observe that Algorithm D requires explicit division only
by $\lscr(v)$, the leading coefficient of $v(x)$, and that step
D2 is carried out exactly $m - n + 1$ times; thus if $u(x)$
and $v(x)$ start with integer coefficients, and if we are working
over the rational numbers, then the only denominators that
appear in the coefficients of $q(x)$ and $r(x)$ are divisors
of $\lscr(v)↑{m-n+1}$. This suggests that we can always find polynomials
$q(x)$ and $r(x)$ such that
$$\lscr(v)↑{m-n+1}u(x) = q(x)v(x) + r(x),\qquad\\deg(r) < n,\eqno
(8)$$
where $m =\\deg(u)$ and $n =\\deg(v)$,
for any polynomials $u(x)$ and $v(x) ≠ 0$, provided that $m≥n$.

\algbegin Algorithm R (Pseudo-division of polynomials).
Given polynomials
$$u(x) = u↓mx↑m +\cdots + u↓1x + u↓0,\qquad v(x)
= v↓nx↑n +\cdots + v↓1(x) + v↓0,$$
where $v↓n ≠ 0$ and $m ≥ n ≥ 0$, this algorithm
finds polynomials $q(x) = q↓{m-n}x↑{m-n} +\cdots
+ q↓0$ and $r(x) = r↓{n-1}x↑{n-1} +\cdots + r↓0$
satisfying (8).

\algstep R1. [Iterate on $k$.] Do step
R2 for $k = m - n$, $m - n - 1$, $\ldotss$, 0; then the algorithm
terminates with $(r↓{n-1},\ldotss,r↓0)=(u↓{n-1}, \ldotss, u↓0)$.

\algstep R2. [Multiplication loop.] Set $q↓k ← u↓{n+k}v↑{k}↓{n}$,
and then set $u↓j ← v↓nu↓j - u↓{n+k}v↓{j-k}$ for $j = n + k
- 1$, $n + k - 2$, $\ldotss$, 0.\xskip (When $j < k$ this means that $u↓j
← v↓nu↓j$, since we treat $v↓{-1}$, $v↓{-2}$, $\ldots$ as zero.
These multiplications could have been avoided if we had started the algorithm
by replacing $u↓t$ by $v↑{m-n-t}↓{n}u↓t$, for $0 ≤ t < m - n$.)\quad\blackslug
%folio 524 galley 4 (C) Addison-Wesley 1978	*
\def\\#1({\mathop{\hjust{#1}}(}\def\+#1\biglp{\mathop{\hjust{#1}}\biglp}
\yyskip An example calculation appears below in
(10). It is easy to prove the validity of Algorithm R by induction
on $m - n$, since each execution of step R2 essentially replaces
$u(x)$ by $\lscr(v)u(x) - \lscr(u)x↑kv(x)$, where $k =\\deg(u)
-\\deg(v)$. Note that no division whatever is used in this
algorithm; the coefficients of $q(x)$ and $r(x)$ are themselves
certain polynomial functions of the coefficients of $u(x)$ and
$v(x)$. If $v↓n = 1$, the algorithm is identical to Algorithm
D\null. If $u(x)$ and $v(x)$ are polynomials over a unique factorization
domain, we can prove as before that the polynomials $q(x)$ and
$r(x)$ are unique; therefore another way to do the pseudo-division
over a unique factorizarion domain is to multiply $u(x)$ by
$v↑{m-n+1}↓{n}$ and apply Algorithm\penalty999\ D\null, knowing that all the
quotients in step D2 will exist.

Algorithm R can be extended to a ``generalized
Euclidean algorithm'' for primitive polynomials over a unique
factorization domain, in the following way: Let $u(x)$ and $v(x)$
be primitive polynomials with $\\deg(u) ≥\\deg(v)$, and determine
$r(x)$ satisfying (8) by means of Algorithm R. Now $\gcd\biglp
u(x), v(x)\bigrp =\gcd\biglp v(x), r(x)\bigrp$:  For any
common divisor of $u(x)$ and $v(x)$ divides $v(x)$ and $r(x)$;
conversely, any common divisor of $v(x)$ and $r(x)$ divides
$\lscr(v)↑{m-n+1}u(x)$, and it must be primitive $\biglp$since
$v(x)$ is primitive$\bigrp$ so it divides $u(x)$. If $r(x) = 0$,
we therefore have $\gcd\biglp u(x), v(x)\bigrp = v(x)$; on the other hand if $r(x)
≠ 0$, we have $\gcd\biglp v(x), r(x)\bigrp = \gcd\biglp v(x),
\+pp\biglp(r(x)\bigrp\bigrp$ since $v(x)$ is primitive, so the process can
be iterated.

\algbegin Algorithm E (Generalized Euclidean algorithm).
Given nonzero polynomials $u(x)$
and $v(x)$ over a unique factorization domain $S$, this algorithm
calculates a greatest common divisor of $u(x)$ and $v(x)$. We
assume that auxiliary algorithms exist to calculate greatest
common divisors of elements of $S$, and to divide $a$ by $b$
in $S$ when $b ≠ 0$ and $a$ is a multiple of $b$.

\algstep E1. [Reduce to primitive.] Set
$d ← \gcd\biglp\\cont(u),\\cont(v)\bigrp $, using the assumed
algorithm for calculating greatest common divisors in $S$.\xskip$\biglp$Note
that cont$(u)$ is a greatest common divisor of the coefficients
of $u(x)$.$\bigrp$\xskip Replace $u(x)$ by the polynomial $u(x)/\\cont(u)
=\+pp\biglp u(x)\bigrp$; similarly, replace $v(x)$ by $\+pp\biglp
v(x)\bigrp$.

\algstep E2. [Pseudo-division.] Calculate $r(x)$ using Algorithm
R.\xskip$\biglp$It is unnecessary to calculate the quotient polynomial
$q(x)$.$\bigrp$\xskip If $r(x) = 0$, go to E4. If deg$(r) = 0$, replace
$v(x)$ by the constant polynomial ``1'' and go to E4.

\algstep E3. [Make remainder primitive.] Replace $u(x)$ by $v(x)$
and replace $v(x)$ by $\+pp\biglp r(x)\bigrp $. Go back to step
E2.\xskip (This is the ``Euclidean step,'' analogous to the other
instances of Euclid's algorithm that we have seen.)

\algstep E4. [Attach the content.] The algorithm terminates,
with $d \cdot v(x)$ as the answer.\quad\blackslug

\yyskip As an example of
Algorithm E\null, let us calculate the greatest common divisor of
$$\baselineskip15pt\eqalign{u(x) ⊗ = x↑8 + x↑6 - 3x↑4 - 3x↑3 + 8x↑2 + 2x - 5,\cr
v(x)⊗=3x↑6+5x↑4-4x↑2-9x+21,\cr}\eqno(9)$$
over the integers. These polynomials are primitive, so step E1 sets $d←1$.
In step E2 we have the pseudo-division
$$\def\\{\lower2.323pt\vjust to 12pt{}}\baselineskip0pt\lineskip0pt
\vcenter{\halign{$\hfill#$\cr
\lower2.732pt\vjust to 12pt{}1\9\90\9\9{-6}\cr
\\3\90\95\90\9{-4}\9{-9}\921\9\overline{\vcenter{\vskip-.818pt
\hjust{\raise1pt\hjust{$\bigrp$}$\91\90\9\9\9\91\90\9\9{-3}\9{-3}\9\98\9\92\9\9\9
{-5}$}\vskip.182pt}}\cr
\\3\90\9\9\9\93\90\9\9{-9}\9{-9}\924\9\96\9\9{-15}\cr
\underline{\\3\90\9\9\9\95\90\9\9{-4}\9{-9}\921\9\9\9\9\9\9\9\9\9}\cr
\\0\9\9{-2}\90\9\9{-5}\9\9\90\9\93\9\96\9\9{-15}\cr
\\0\9\9{-6}\90\9{-15}\9\9\90\9\99\918\9\9{-45}\cr
\underline{\\0\9\9\9\90\90\9\9\9\90\9\9\90\9\90\9\90\9\9\9\9\90}\cr
\\{-6}\90\9{-15}\9\9\90\9\99\918\9\9{-45}\cr
\\{-18}\90\9{-45}\9\9\90\927\954\9{-135}\cr
\underline{\\{-18}\90\9{-30}\9\9\90\924\954\9{-126}}\cr
\\{-15}\9\9\90\9\93\9\90\9\9\9{-9}\cr}}\eqno(10)$$
Here the quotient $q(x)$ is $1\cdot3↑2x↑2+0\cdot3↑1x+{-6}\cdot3↑0$; we have
$$27u(x)\;=\;v(x)(9x↑2-6)\;+\;(-15x↑4+3x↑2-9).\eqno(11)$$
Now step E3 replaces $u(x)$ by $v(x)$ and $v(x)$ by $\+pp\biglp r(x)\bigrp=5x↑4
-x↑2+3$. The subsequent calculation may be summarized as follows, writing only
the coefficients:
$$\vjust{\baselineskip14pt\halign{$\hfill#$⊗$\hskip15pt\hfill#$⊗$\hskip15pt\hfill
#$\cr
u(x)\hfill⊗v(x)\hfill⊗r(x)\hfill\cr
\noalign{\vskip2pt}
1,0,1,0,-3,-3,8,2,-5⊗3,0,5,0,-4,-9,21⊗-15,0,3,0,-9\cr
3,0,5,0,-4,-9,21⊗5,0,-1,0,3⊗-585,-1125,2205\cr
5,0,-1,0,3⊗13,25,-49⊗-233150,307500\cr
13,25,-49⊗4663,-6150⊗143193869\cr}}\eqno(12)$$

It is instructive to compare this calculation with the computation of the same
greatest common divisor over the {\sl rational\/} numbers, instead of over the
integers, by using Euclid's algorithm for polynomials over a field as described
earlier in this section. The following surprisingly complicated sequence of
results occurs:
$$\vjust{\baselineskip15pt\halign{$\hfill#$⊗\qquad$\hfill#$\cr
u(x)\hfill⊗v(x)\hfill\cr
\noalign{\vskip2pt}
1,0,1,0,-3,-3,8,2,5⊗3,0,5,0,-4,-9,21\cr
3,0,5,0,-4,-9,21⊗-{5\over9},0,{1\over9},0,-{1\over3}\cr
-{5\over9},0,{1\over9},0,-{1\over3}⊗-{117\over25},-9,{441\over25}\cr
-{117\over25},-9,{441\over25}⊗{233150\over19773},-{102500\over6591}\cr
{233150\over19773},-{102500\over6591}⊗-{1288744821\over543589225}\cr}}\eqno(13)$$
%folio 526 galley 5 (C) Addison-Wesley 1978	*
\def\\#1({\mathop{\hjust{#1}}(}\def\+#1\biglp{\mathop{\hjust{#1}}\biglp}
To improve that algorithm, we can reduce
$u(x)$ and $v(x)$ to monic polynomials at each step, since this
removes ``unit'' factors that make the coefficients more complicated
than necessary; this is actually Algorithm E over the rationals:
$$\vjust{\baselineskip15pt\halign{$\hfill#$⊗\qquad$\hfill#$\cr
u(x)\hfill⊗v(x)\hfill\cr
\noalign{\vskip2pt}
1,0,1,0,-3,-3,8,2,5⊗3,0,5,0,-4,-9,21\cr
1,0,{5\over3},0,-{4\over3},-3,7⊗1,0,-{1\over5},0,{3\over5}\cr
1,0,-{1\over5},0,{3\over5}⊗1,{25\over13},-{49\over13}\cr
1,{25\over13},-{49\over13}⊗1,-{6150\over4663}\cr
1,-{6150\over4663}⊗1\cr}}\eqno(14)$$

In both (13) and (14) the sequence of polynomials
is essentially the same as (12), which was obtained by Algorithm
E over the integers; the only difference is that the polynomials
have been multiplied by certain rational numbers. Whether we
have $5x↑4 - x↑2 + 3$ or $-{5\over 9}x↑4 + {1\over 9}x↑2 -
{1\over 3}$ or $x↑4 - {1\over 5}x↑2 + {3\over 5}$, the computations
are essentially the same. But either algorithm using rational
arithmetic will run noticeably slower than the all-integer Algorithm
E\null, since rational arithmetic requires many more evaluations
of gcd's of integers within each step. Therefore it is definitely
preferable to use the all-integer algorithm instead of rational
arithmetic, when the gcd of polynomials with integer or rational
coefficients is desired.

It is also instructive to compare the above calculations
with (6) above, where we determined the gcd of the same polynomials
$u(x)$ and $v(x)$ modulo 13 with considerably less labor. Since
$\lscr(u)$ and $\lscr(v)$ are not multiples of 13, the fact that
$\gcd\biglp u(x), v(x)\bigrp = 1$ modulo 13 is sufficient to
prove that $u(x)$ and $v(x)$ are relatively prime over the integers
(and therefore over the rational numbers); we will return to
this time-saving observation at the close of Section 4.6.2.

\subsectionbegin{The subresultant algorithm} An ingenious
algorithm that is generally superior to Algorithm E\null, and that
gives us further information about Algorithm E's behavior, was
discovered by George E. Collins [{\sl JACM \bf 14} (1967),
128--142] and subsequently improved by W. S. Brown and J. F. Traub
[{\sl JACM \bf18} (1971), 505--514; see also W. S. Brown, {\sl ACM
Trans.\ Math.\ Software \bf4} (1978), to appear].
This algorithm avoids the calculation of primitive
part in step E3, dividing instead by an element of $S$ that
is known to be a factor of $r(x)$:

\algbegin Algorithm C (Greatest common divisor over a unique
factorization domain). This algorithm has the same input
and output assumptions as Algorithm E\null, and has the advantage
that fewer calculations of greatest common divisors of coefficients
are needed.

\algstep C1. [Reduce to primitive.] As in
step E1 of Algorithm E\null, set $d ← \gcd\biglp\\cont(u),\penalty0\\cont(v)\bigrp
$, and replace $\biglp u(x), v(x)\bigrp$ by $\biglp\+pp\biglp u(x)\bigrp,
\+pp\biglp v(x)\bigrp\bigrp$. Also set $g←h ← 1$.

\algstep C2. [Pseudo-division.] Set $\delta ← \\deg(u)-\\deg(v)$.
Calculate $r(x)$ using Algorithm\penalty999\ R\null. If $r(x) = 0$, go to C4.
If deg$(r) = 0$, replace $v(x)$ by the constant polynomial ``1''
and go to C4.

\algstep C3. [Adjust remainder.] Replace the polynomial $u(x)$
by $v(x)$, and replace $v(x)$ by $r(x)/gh↑\delta$.\xskip$\biglp$At this point all
coefficients of $r(x)$ are multiples of $gh↑\delta$.$\bigrp$\xskip Then set $g ←
\lscr(u)$, $h←h↑{1-\delta}g↑\delta$ and return to C2.\xskip$\biglp$The new value
of $h$ will be in the domain $S$, even if $\delta>1$.$\bigrp$

\algstep C4. [Attach the content.] The algorithm terminates,
with $d \cdot\+pp\biglp v(x)\bigrp$ as the answer.\quad\blackslug

\yyskip If we apply this algorithm
to the polynomials (9) considered earlier, the following sequence
of results is obtained at the beginning of step C2:
$$\vjust{\baselineskip15pt\halign{$\hfill#$⊗\qquad$\hfill#$⊗\qquad$\hfill#$⊗\qquad
$\hfill#$\cr
u(x)\hfill⊗v(x)\hfill⊗g⊗h\cr
\noalign{\vskip2pt}
1,0,1,0,-3,-3,8,2,5⊗3,0,5,0,-4,-9,21⊗1⊗1\cr
3,0,5,0,-4,-9,21⊗-15,0,3,0,-9⊗3⊗9\cr
-15,0,3,0,-9⊗65,125,-245⊗-15⊗25\cr
65,125,-245⊗-9826,12300⊗65⊗169\cr}}\eqno(15)$$
At the conclusion of the algorithm, $r(x)/gh↑\delta = 260708$.

The sequence of polynomials consists of integral
multiples of the polynomials in the sequence produced by Algorithm
E\null. In spite of the fact that
the polynomials are not reduced to primitive form, the coefficients
are kept to a reasonable size because of the reduction factor
in step C3.

In order to analyze Algorithm C and to prove that
it is valid, let us call the sequence of polynomials it produces
$u↓1(x)$, $u↓2(x)$, $u↓3(x)$, $\ldotss$, where $u↓1(x) = u(x)$ and
$u↓2(x) = v(x)$. Let $\delta↓j=n↓j-n↓{j+1}$ for $j≥1$, where $n↓j=\\deg(u↓j)$;
and let $g↓1=h↓1=1$, $g↓j=\lscr(u↓j)$, $h↓j=h↓{j-1}↑{1-\delta↓{j-1}}g↓{\!j}↑{\delta
↓{j-1}}$ for $j≥2$. Then we have
$$\baselineskip15pt\eqalign{
g↓2↑{\delta↓1+1}u↓1(x)⊗=u↓2(x)q↓1(x)+g↓1h↓1↑{\delta↓1}u↓3(x),\qquad n↓3<n↓2;\cr
g↓3↑{\delta↓2+1}u↓2(x)⊗=u↓3(x)q↓2(x)+g↓2h↓2↑{\delta↓2}u↓4(x),\qquad n↓4<n↓3;\cr
g↓4↑{\delta↓3+1}u↓3(x)⊗=u↓4(x)q↓3(x)+g↓3h↓3↑{\delta↓3}u↓5(x),\qquad n↓5<n↓4;\cr}
\eqno(16)$$
and so on. The process terminates when $n↓{k+1}
=\\deg(u↓{k+1}) ≤0$. We must show that $u↓3(x)$, $u↓4(x)$, $\ldotss
$, have coefficients in $S$, i.e., that the factors $g↓jh↓j↑{\delta↓j}$
evenly divide the remainders, and we must also
show that the $h↓j$ values all belong to $S$. The proof is rather
involved, and it can be most easily understood by considering
an example.

\topinsert{\tablehead{Table 1}
\vskip3pt
\ctrline{COEFFICIENTS IN ALGORITHM C}
\vskip6pt
\baselineskip0pt\lineskip0pt
\def\\{\vrule height 8.5pt depth 2.5pt}
\def\¬{\vrule height 2pt}
\def\+#1{\hjust to 0pt{\hskip 0pt minus 100pt #1\hskip 0pt minus 100pt}}
\halign to size{$\ctr{#}$\tabskip0pt plus 10pt⊗#⊗$\ctr{#}$⊗$\ctr{#}$⊗\!
$\ctr{#}$⊗$\ctr{#}$⊗$\ctr{#}$⊗$\ctr{#}$⊗$\ctr{#}$⊗$\ctr{#}$⊗$\ctr{#}$⊗$\ctr{#}$⊗\!
$\ctr{#}$⊗$\ctr{#}$⊗$\ctr{#}$⊗$\ctr{#}$⊗#⊗$\ctr{#}$⊗#⊗$\hfill#$\tabskip0pt\cr
\+{Row}⊗\\⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗\\⊗\+{Multiply}⊗\\⊗\hjust{\hskip-5pt Replace\hskip-10pt}\cr
\+{name}⊗\\⊗⊗⊗⊗⊗⊗⊗\hjust{ R\spose{ow}}⊗⊗⊗⊗⊗⊗⊗⊗\\⊗\+{by}⊗\\⊗\hjust{\hskip-10pt
by row\hskip-8pt
}\cr
⊗\¬⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗\¬⊗⊗\¬\cr
\noalign{\moveleft12pt\hjust to 372pt{\leaders\hrule\hfill}}
⊗\¬⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗\¬⊗⊗\¬\cr
A↓5⊗\\⊗a↓8⊗a↓7⊗a↓6⊗a↓5⊗a↓4⊗a↓3⊗a↓2⊗a↓1⊗a↓0⊗0⊗0⊗0⊗0⊗0⊗\\⊗b↓6↑3⊗\\⊗C↓5\cr
A↓4⊗\\⊗0⊗a↓8⊗a↓7⊗a↓6⊗a↓5⊗a↓4⊗a↓3⊗a↓2⊗a↓1⊗a↓0⊗0⊗0⊗0⊗0⊗\\⊗b↓6↑3⊗\\⊗C↓4\cr
A↓3⊗\\⊗0⊗0⊗a↓8⊗a↓7⊗a↓6⊗a↓5⊗a↓4⊗a↓3⊗a↓2⊗a↓1⊗a↓0⊗0⊗0⊗0⊗\\⊗b↓6↑3⊗\\⊗C↓3\cr
A↓2⊗\\⊗0⊗0⊗0⊗a↓8⊗a↓7⊗a↓6⊗a↓5⊗a↓4⊗a↓3⊗a↓2⊗a↓1⊗a↓0⊗0⊗0⊗\\⊗b↓6↑3⊗\\⊗C↓2\cr
A↓1⊗\\⊗0⊗0⊗0⊗0⊗a↓8⊗a↓7⊗a↓6⊗a↓5⊗a↓4⊗a↓3⊗a↓2⊗a↓1⊗a↓0⊗0⊗\\⊗b↓6↑3⊗\\⊗C↓1\cr
A↓0⊗\\⊗0⊗0⊗0⊗0⊗0⊗a↓8⊗a↓7⊗a↓6⊗a↓5⊗a↓4⊗a↓3⊗a↓2⊗a↓1⊗a↓0⊗\\⊗b↓6↑3⊗\\⊗C↓0\cr
B↓7⊗\\⊗b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗\\⊗⊗\\\cr
B↓6⊗\\⊗0⊗b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0⊗0⊗0⊗0⊗0⊗0⊗0⊗\\⊗⊗\\\cr
B↓5⊗\\⊗0⊗0⊗b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0⊗0⊗0⊗0⊗0⊗0⊗\\⊗⊗\\\cr
B↓4⊗\\⊗0⊗0⊗0⊗b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0⊗0⊗0⊗0⊗0⊗\\⊗⊗\\\cr
B↓3⊗\\⊗0⊗0⊗0⊗0⊗b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0⊗0⊗0⊗0⊗\\⊗c↓4↑3/b↓6↑5⊗\\⊗D↓3\cr
B↓2⊗\\⊗0⊗0⊗0⊗0⊗0⊗b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0⊗0⊗0⊗\\⊗c↓4↑3/b↓6↑5⊗\\⊗D↓2\cr
B↓1⊗\\⊗0⊗0⊗0⊗0⊗0⊗0⊗b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0⊗0⊗\\⊗c↓4↑3/b↓6↑5⊗\\⊗D↓1\cr
B↓0⊗\\⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0⊗\\⊗c↓4↑3/b↓6↑5⊗\\⊗D↓0\cr
C↓5⊗\\⊗0⊗0⊗0⊗0⊗c↓4⊗c↓3⊗c↓2⊗c↓1⊗c↓0⊗0⊗0⊗0⊗0⊗0⊗\\⊗⊗\\\cr
C↓4⊗\\⊗0⊗0⊗0⊗0⊗0⊗c↓4⊗c↓3⊗c↓2⊗c↓1⊗c↓0⊗0⊗0⊗0⊗0⊗\\⊗⊗\\\cr
C↓3⊗\\⊗0⊗0⊗0⊗0⊗0⊗0⊗c↓4⊗c↓3⊗c↓2⊗c↓1⊗c↓0⊗0⊗0⊗0⊗\\⊗⊗\\\cr
C↓2⊗\\⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗c↓4⊗c↓3⊗c↓2⊗c↓1⊗c↓0⊗0⊗0⊗\\⊗⊗\\\cr
C↓1⊗\\⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗c↓4⊗c↓3⊗c↓2⊗c↓1⊗c↓0⊗0⊗\\⊗d↓2↑2b↓6↑4/c↓4↑5⊗\\⊗E↓1\cr
C↓0⊗\\⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗c↓4⊗c↓3⊗c↓2⊗c↓1⊗c↓0⊗\\⊗d↓2↑2b↓6↑4/c↓4↑5⊗\\⊗E↓0\cr
D↓3⊗\\⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗d↓2⊗d↓1⊗d↓0⊗0⊗0⊗0⊗\\⊗⊗\\\cr
D↓2⊗\\⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗d↓2⊗d↓1⊗d↓0⊗0⊗0⊗\\⊗⊗\\\cr
D↓1⊗\\⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗d↓2⊗d↓1⊗d↓0⊗0⊗\\⊗⊗\\\cr
D↓0⊗\\⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗d↓2⊗d↓1⊗d↓0⊗\\⊗e↓2↑2c↓4↑2/d↓2↑3b↓6↑2⊗\\⊗F↓0\cr
E↓1⊗\\⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗e↓1⊗e↓0⊗0⊗\\⊗⊗\\\cr
E↓0⊗\\⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗e↓1⊗e↓0⊗\\⊗⊗\\\cr
F↓0⊗\\⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗f↓0⊗\\⊗⊗\\\cr}}

%folio 528 galley 6 Beginning lost. (C) Addison-Wesley 1978	*
Suppose, as in (15), that $n↓1=8$, $n↓2=6$, $n↓3=4$, $n↓4=2$, $n↓5=1$,
$n↓6=0$, so that $\delta↓1=\delta↓2=\delta↓3=2$, $\delta↓4=\delta↓5=1$.
Let us write $u↓1(x)=a↓8x↑8+a↓7x↑7+\cdots+a↓0$,\xskip
$u↓2(x)=b↓6x↑6+b↓5x↑5+\cdots+b↓0$,\xskip
$\ldotss$,\xskip $u↓5(x)=e↓1x+e↓0$,\xskip $u↓6(x)=f↓0$,\xskip
so that $h↓1=1$, $h↓2=b↓6↑2$,
$h↓3=c↓4↑2/b↓6↑2$, $h↓4=d↓2↑2b↓6↑2/c↓4↑2$. In these terms it is helpful to
consider the array shown in Table 1. For concreteness, let us assume that the
coefficients of the polynomials are integers. We have $b↓6↑3u↓1(x)=u↓2(x)q↓1(x)+
u↓3(x)$; so if we multiply row $A↓5$ by $b↓6↑3$ and subtract appropriate
multiples of rows $B↓7$, $B↓6$, and $B↓5$ $\biglp$corresponding to the
coefficients of $q↓1(x)\bigrp$ we will get row $C↓5$. Similarly, if we multiply
row $A↓4$ by $b↓6↑3$ and subtract multiples of rows $B↓6$, $B↓5$, and $B↓4$,
we get row $C↓4$. In a similar way, we have $c↓4↑3u↓2(x)=u↓3(x)q↓2(x)+b↓6↑5u↓4(x)$;
so we can multiply row $B↓3$ by $c↓4↑3$, subtract integer multiples of rows
$C↓5$, $C↓4$, and $C↓3$, then divide by $b↓6↑5$ to obtain row $D↓3$. 

In order to prove that $u↓4(x)$ has integer coefficients, let us consider the
matrix
$$\cpile{A↓2\cr A↓1\cr A↓0\cr B↓4\cr B↓3\cr B↓2\cr B↓1\cr B↓0\cr}\quad
\left(\,\vcenter{\halign{$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9
$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$\cr
a↓8⊗a↓7⊗a↓6⊗a↓5⊗a↓4⊗a↓3⊗a↓2⊗a↓1⊗a↓0⊗0⊗0\cr
0⊗a↓8⊗a↓7⊗a↓6⊗a↓5⊗a↓4⊗a↓3⊗a↓2⊗a↓1⊗a↓0⊗0\cr
0⊗0⊗a↓8⊗a↓7⊗a↓6⊗a↓5⊗a↓4⊗a↓3⊗a↓2⊗a↓1⊗a↓0\cr
b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0⊗0⊗0⊗0⊗0\cr
0⊗b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0⊗0⊗0⊗0\cr
0⊗0⊗b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0⊗0⊗0\cr
0⊗0⊗0⊗b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0⊗0\cr
0⊗0⊗0⊗0⊗b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0\cr}}\,\right)=M.\eqno(17)$$
The indicated row operations and a permutation of rows
will transform $M$ into
$$\cpile{B↓4\cr B↓3\cr B↓2\cr B↓1\cr B↓0\cr C↓2\cr C↓1\cr D↓0\cr}\quad
\left(\,\vcenter{\halign{$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9
$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$\cr
b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0⊗0⊗0⊗0⊗0\cr
0⊗b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0⊗0⊗0⊗0\cr
0⊗0⊗b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0⊗0⊗0\cr
0⊗0⊗0⊗b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0⊗0\cr
0⊗0⊗0⊗0⊗c↓4⊗c↓3⊗c↓2⊗c↓1⊗c↓0⊗0⊗0\cr
0⊗0⊗0⊗0⊗0⊗c↓4⊗c↓3⊗c↓2⊗c↓1⊗c↓0⊗0\cr
0⊗0⊗0⊗0⊗0⊗0⊗c↓4⊗c↓3⊗c↓2⊗c↓1⊗c↓0\cr
0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗d↓2⊗d↓1⊗d↓0\cr}}\,\right)=M↑\prime.\eqno(18)$$
Because of the way $M↑\prime$ has been derived from
$M$, we have
$$b↓6↑3 \cdot b↓6↑3 \cdot b↓6↑3 \cdot
(c↓4↑3/b↓6↑5) \cdot\det M↓0 = \pm\det M↑\prime↓{\!0},\eqno(19)$$
if $M↓0$ and $M↑\prime↓{\!0}$ represent any square
matrices obtained by selecting eight corresponding columns from
$M$ and $M↑\prime $. For example, let us select the first seven
columns and the column containing $d↓1$; then
$$b↓6↑3\cdot b↓6↑3\cdot b↓6↑3\cdot(c↓4↑3/b↓6↑5)\cdot\det\left(\,\vcenter{
\halign{$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9
$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$\cr
a↓8⊗a↓7⊗a↓6⊗a↓5⊗a↓4⊗a↓3⊗a↓2⊗0\cr
0⊗a↓8⊗a↓7⊗a↓6⊗a↓5⊗a↓4⊗a↓3⊗a↓0\cr
0⊗0⊗a↓8⊗a↓7⊗a↓6⊗a↓5⊗a↓4⊗a↓1\cr
b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0⊗0\cr
0⊗b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗0\cr
0⊗0⊗b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗0\cr
0⊗0⊗0⊗b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓0\cr
0⊗0⊗0⊗0⊗b↓6⊗b↓5⊗b↓4⊗b↓1\cr}}\,\right)=\pm b↓6↑4\cdot c↓4↑3\cdot d↓1.$$
Since $b↓6c↓4 ≠ 0$, this proves that $d↓1$ is an integer.
Similarly, $d↓2$ and $d↓0$ are integers.

In general, we can show that $u↓{j+1}(x)$ has integer
coefficients in a similar manner. If we start with the matrix
$M$ consisting of rows $A↓{n↓2-n↓j}$ through
$A↓0$ and $B↓{n↓1-n↓j}$ through $B↓0$, and if
we perform the row operations indicated in Table 1, we will
obtain a matrix $M↑\prime$ consisting in some order of rows
$B↓{n↓1-n↓j}$ through $B↓{n↓3-n↓j+1}$,\xskip
$C↓{n↓2-n↓j}$ through $C↓{n↓4-n↓j+1}$,\xskip $\ldotss$,\xskip $P↓{n↓{j-2}-n↓j}$
through $P↓1$,\xskip $Q↓{n↓{j-1}-n↓j}$ through $Q↓0$,\xskip and finally $R↓0$
$\biglp$a row containing the coefficients of $u↓{j+1}(x)\bigrp$. Extracting
appropriate columns shows that
$$\twoline{\hskip-10pt
(g↓2↑{\delta↓1+1}/g↓1h↓1↑{\delta↓1})↑{n↓2-n↓j+1}(g↓3↑{\delta↓2+1}/g↓2h↓2↑{\delta↓2}
)↑{n↓3-n↓j+1}\ldotss(g↓{\!j}↑{\delta↓{j-1}+1}/g↓{j-1}h↓{\!j-1}↑{\delta↓{j-1}})↑
{n↓j-n↓j+1}\det M↓0}{3pt}{=\pm g↓2↑{n↓1-n↓3}g↓3↑{n↓2-n↓4}\ldotss g↓{\!j-1}↑{n↓{j-2}
-n↓j}g↓{\!j}↑{n↓{j-1}-n↓j+1}r↓t,\quad(19)\hskip-10pt}$$
where $r↓t$ is a given coefficient of $u↓{j+1}(x)$ and $M↓0$ is a submatrix of
$M$. The $h$'s have been chosen very cleverly so that this equation simplifies to
$$\det M↓0=\pm \,r↓t\eqno(20)$$
(see exercise 24). Therefore {\sl every coefficient of $u↓{j+1}(x)$ can be
expressed as the determinant of an $(n↓1+n↓2-2n↓j+2)\times(n↓1+n↓2-2n↓j+2)$
matrix whose elements are coefficients of $u(x)$ and $v(x)$.}

It remains to be shown that the cleverly-chosen $h$'s also are integers. A
similar technique applies: Let's look, for example, at the matrix
$$\cpile{A↓1\cr A↓0\cr B↓3\cr B↓2\cr B↓1\cr B↓0\cr}\quad
\left(\,\vcenter{\halign{$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9
$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$\cr
a↓8⊗a↓7⊗a↓6⊗a↓5⊗a↓4⊗a↓3⊗a↓2⊗a↓1⊗a↓0⊗0\cr
0⊗a↓8⊗a↓7⊗a↓6⊗a↓5⊗a↓4⊗a↓3⊗a↓2⊗a↓1⊗a↓0\cr
b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0⊗0⊗0⊗0\cr
0⊗b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0⊗0⊗0\cr
0⊗0⊗b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0⊗0\cr
0⊗0⊗0⊗b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0\cr}}\,\right)=M.\eqno(21)$$
Row operations as specified in Table 1, and permutation of rows, leads to
$$\cpile{B↓3\cr B↓2\cr B↓1\cr B↓0\cr C↓1\cr C↓0\cr}\quad
\left(\,\vcenter{\halign{$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9
$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$\cr
b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0⊗0⊗0⊗0\cr
0⊗b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0⊗0⊗0\cr
0⊗0⊗b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0⊗0\cr
0⊗0⊗0⊗b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0\cr
0⊗0⊗0⊗0⊗c↓4⊗c↓3⊗c↓2⊗c↓1⊗c↓0⊗0\cr
0⊗0⊗0⊗0⊗0⊗c↓4⊗c↓3⊗c↓2⊗c↓1⊗c↓0\cr}}\,\right)=M↑\prime;\eqno(22)$$
hence if we consider any submatrices $M↓0$ and $M↓{\!0}↑\prime$ obtained by
selecting six corresponding columns of $M$ and $M↑\prime$ we have
$$b↓6↑3\cdot b↓6↑3 \cdot b↓6↑3\cdot\det M↓0=\pm\det M↓{\!0}↑\prime.$$
When $M↓0$ is chosen to be the first six columns of $M$, we find that
$\det M↓0=\pm c↓4↑2/b↓6↑2=\pm h↓3$, so $h↓3$ is an integer.

In general, to show that $h↓j$ is an integer for $j≥3$, we start with the
matrix $M$ consisting of rows $A↓{n↓2-n↓j-1}$ through $A↓0$ and $B↓{n↓1-n↓j-1}$
through $B↓0$; then we perform appropriate row operations until obtaining a
matrix $M↑\prime$ consisting of rows $B↓{n↓1-n↓j-1}$ through $B↓{n↓3-n↓j}$,\xskip
$C↓{n↓2+n↓j-1}$ through $C↓{n↓4-n↓j}$,\xskip $\ldotss$,\xskip
$P↓{n↓{j-2}-n↓j-1}$ through\penalty999\
$P↓0$,\xskip $Q↓{n↓{j-1}-n↓j-1}$ through $Q↓0$. Letting $M↓0$ be the first
$n↓1+n↓2-2n↓j$ columns of $M$, we obtain
$$\twoline{(g↓2↑{\delta↓1+1}/g↓1h↓1↑{\delta↓1})↑{n↓2-n↓j}(g↓3↑{\delta↓2+1}
/g↓2h↓2↑{\delta↓2})↑{n↓3-n↓j}\ldotss(g↓j↑{\delta↓{j-1}+1}/g↓{j-1}h↓{\!j-1}↑{\delta
↓{j-1}})↑{n↓j-n↓j}\det M↓0}{3pt}{=\pm g↓2↑{n↓1-n↓3}g↓3↑{n↓2-n↓4}\ldotss g↓{\!j-1}↑
{n↓{j-2}-n↓j}g↓{\!j}↑{n↓{j-1}-n↓j},\quad(23)\hskip-10pt}$$
an equation that neatly simplifies to
$$\det M↓0=\pm h↓j.\eqno(24)$$
(This proof, although stated for the domain of integers, obviously applies to any
unique factorization domain.)
%folio 530 galley 7 (C) Addison-Wesley 1978	*

In the process of verifying Algorithm C\null, 
we have also learned that every element
of $S$ dealt with by the algorithm can be expressed as a determinant whose
entries are the coefficients of the primitive parts of the original polynomials.
A well-known theorem of Hadamard (see exercise 15) states that
$$|\det(a↓{ij})|≤\prod↓{1≤i≤n}\;\bigglp\sum↓{1≤j≤n}a↓{ij}↑2\biggrp↑{1/2};
\eqno(25)$$
therefore an upper bound for the maximum coefficient
appearing in the polynomials computed by Algorithm C is
$$N↑{m+n}(m + 1)↑{n/2}(n + 1)↑{m/2},\eqno (26)$$
if all coefficients of the given polynomials $u(x)$
and $v(x)$ are bounded by $N$ in absolute value. This same
upper bound applies to the coefficients of all polynomials $u(x)$ and
$v(x)$ computed during the execution of Algorithm E\null, 
since the polynomials obtained
in Algorithm E are always divisors of the polynomials obtained
in Algorithm C.

This upper bound on the coefficients is extremely
gratifying, because it is much better than we would ordinarily
have a right to expect. For example, suppose we would perform Algorithm
E or Algorithm C with {\sl no} correction in step E3 or C3,
just replacing $v(x)$ by $r(x)$. This is the simplest
gcd algorithm, and it is the one that traditionally appears in
textbooks on algebra (for theoretical purposes, not intended
for practical calculations).\xskip If we suppose that $\delta↓1=\delta↓2=
\cdots = 1$, we find that the coefficients of $u↓3(x)$
are bounded by $N↑3$, the coefficients of $u↓4(x)$ are bounded
by $N↑7$, those of $u↓5(x)$ by $N↑7$, $\ldotss $; the coefficients of $u↓k(x)$
are bounded by $N↑{a↓k}$, where $a↓k = 2a↓{k-1} +
a↓{k-2}$. Thus the upper bound, in place of (25) for $m = n + 1$, would
be approximately
$$N↑{0.5(2.414)↑n},\eqno (26)$$
and experiments show that the simple algorithm
does in fact have this behavior; the number of digits in the
coefficients grows exponentially at each step! In Algorithm
E, by contrast, the growth in number of digits is only slightly more than
linear at most.

Another byproduct of our proof of Algorithm C is the fact that the degrees of the
polynomials will almost always decrease by 1 at each step, so that the number of
iterations of step C2 (or E2) will usually be deg$(v)$ if the given polynomials
are ``random.'' In order to see why this happens, note for example that we could
have chosen the first eight columns of $M$ and $M↑\prime$ in (16) and (17),
and then we would have found that $u↓4(x)$ has degree less than 3 if and only if
$d↓3=0$, that is, if and only if
$$\det\left(\,\vcenter{
\halign{$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9
$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$⊗\9$\ctr{#}$\cr
a↓8⊗a↓7⊗a↓6⊗a↓5⊗a↓4⊗a↓3⊗a↓2⊗a↓1\cr
0⊗a↓8⊗a↓7⊗a↓6⊗a↓5⊗a↓4⊗a↓3⊗a↓2\cr
0⊗0⊗a↓8⊗a↓7⊗a↓6⊗a↓5⊗a↓4⊗a↓3\cr
b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0⊗0\cr
0⊗b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1⊗b↓0\cr
0⊗0⊗b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2⊗b↓1\cr
0⊗0⊗0⊗b↓6⊗b↓5⊗b↓4⊗b↓3⊗b↓2\cr
0⊗0⊗0⊗0⊗b↓6⊗b↓5⊗b↓4⊗b↓3\cr}}\,\right)=0.$$
In general, $\delta↓j$ will be greater than 1 for $j>1$ if and only if a similar
determinant in the coefficients of $u(x)$ and $v(x)$ is zero. Since such a
determinant is a nonzero multivariate polynomial in the coefficients, it will be
nonzero ``almost always,'' or ``with probability 1.''\xskip(See exercise 16 for a
more precise formulation of this statement, and see exercise 4 for a related
proof.)\xskip The example polynomials in (15) have both $\delta↓2$ and $\delta↓3$
equal to 2, so they are exceptional indeed.

The considerations above can be used to derive
the well-known fact that two polynomials are relatively prime
if and only if their ``resultant'' is nonzero; the resultant
is a determinant having the form of rows $A↓5$ through $A↓0$
and $B↓7$ through $B↓0$ in Table 1.\xskip$\biglp$This
is ``Sylvester's determinant'';
see exercise 12. Further properties of resultants are discussed
in B. L. van der Waerden, {\sl Modern Algebra}, tr.\ by Fred
Blum (New York: Ungar, 1949), Sections 27--28.$\bigrp$\xskip From the standpoint
discussed above, we could say that the gcd is ``almost always''
of degree zero, since Sylvester's determinant is almost never
zero. But many calculations of practical interest would never
be undertaken if there weren't some reasonable chance that the
gcd would be a polynomial of positive degree.

We can see exactly what happens during Algorithms
E and C when the gcd is not 1 by considering $u(x) = w(x)u↓1(x)$ and
$v(x) = w(x)u↓2(x)$, where $u↓1(x)$ and $u↓2(x)$ are relatively
prime and $w(x)$ is primitive. Then if the polynomials $u↓1(x)$,
$u↓2(x)$, $u↓3(x)$, $\ldots$ are obtained when Algorithm E works on
$u(x) = u↓1(x)$ and $v(x) = u↓2(x)$, it is easy to show that
the sequence obtained for $u(x) = w(x)u↓1(x)$ and $v(x) = w(x)u↓2(x)$
is simply $w(x)u↓1(x)$, $w(x)u↓2(x)$, $w(x)u↓3(x)$, $w(x)u↓4(x)$, $\ldotss\,$.
With Algorithm C the behavior is different; if the polynomials
$u↓1(x)$, $u↓2(x)$, $u↓3(x)$, $\ldots$ are obtained when Algorithm
C is applied to $u(x) = u↓1(x)$ and $v(x) = u↓2(x)$, and if
we assume that deg$(u↓{j+1}) =\hjust{deg}(u↓j) - 1$ (which is almost
always true when $j > 1$), then the sequence
$$w(x)u↓1(x),\; w(x)u↓2(x),\;\lscr↑2w(x)u↓3(x),\;\lscr↑4w(x)u↓4(x),
\;\lscr↑6w(x)u↓5(x),\;\ldots\eqno(27)$$
is obtained when Algorithm C is applied to $u(x)
= w(x)u↓1(x)$ and $v(x) = w(x)u↓2(x)$, where $\lscr=\lscr(w)$.\xskip
(See exercise 13.)\xskip So Algorithm E may be superior to Algorithm
C when the primitive part of the greatest common divisor has
a large enough leading coefficient.

\yskip Polynomials remainder sequences such as those in
Algorithm C and E are not useful merely for finding greatest
common divisors; another important application is to the enumeration
of real roots, for a given polynomial in a given interval, according
to the famous theorem of J. Sturm [{\sl M\'em.\ pr\'esentes
par divers savants \bf 6} (Paris, 1835), 271--318]. Let $u(x)$
be a polynomial over the real numbers, having distinct roots.
We shall see in the next section that this is the same as saying
gcd$\biglp u(x), u↑\prime (x)\bigrp = 1$, where $u↑\prime (x)$
is the derivative of $u(x)$; accordingly, there is a polynomial
remainder sequence proving that $u(x)$ is relatively prime
to $u↑\prime (x)$. We set $u↓0(x) = u(x)$, $u↓1(x) = u↑\prime
(x)$, and (following Sturm) we negate the sign of all remainders:
$$\baselineskip15pt
\eqalign{c↓1u↓0(x)⊗=u↓1(x)q↓1(x) - d↓1u↓2(x),\cr
c↓2u↓1(x) ⊗= u↓2(x)q↓2(x) - d↓2u↓3(x),\cr
⊗\9\;\vdots\cr
c↓ku↓{k-1}(x) ⊗= u↓k(x)q↓k(x) - d↓ku↓{k+1}(x),\cr}\eqno(28)$$
for some positive constants $c↓j$ and $d↓j$, where deg$(u↓{k+1})
= 0$. We say that the {\sl variation} $V(u, a)$ of $u(x)$ at $a$
is the number of changes of sign in the sequence $u↓0(a)$, $u↓1(a)$,
$\ldotss$, $u↓{k+1}(a)$, not counting zeros. For example, if the
sequence of signs is 0, +, $-$, $-$, 0, +, +, $-$ we have $V(u, a)
= 3$. Sturm's theorem asserts that {\sl the number of roots
of $u(x)$ in the interval $a < x ≤ b$ is $V(u, a) - V(u, b)$}; and
the proof is surprisingly short (see exercise 22).

\yskip Although Algorithms C and E are interesting, they aren't the whole story.
Important alternative ways to calculate polynomial
gcd's over the integers are discussed at the end of Section
4.6.2. There is also a general determinant-evaluation algorithm that may be said
to include Algorithm C as a special case; see E. H.
Bareiss, {\sl Math.\ Comp.\ \bf 22} (1968), 565--578.

\exbegin{EXERCISES}

\exno 1. [10] Compute the pseudo-quotient
$q(x)$ and pseudo-remainder $r(x)$, namely, the polynomials
satisfying (8), when $u(x) = x↑6 + x↑5 - x↑4 + 2x↑3 + 3x↑2 -
x + 2$ and $v(x) = 2x↑3 + 2x↑2 - x + 3$, over the integers.

\exno 2. [15] What is the greatest common divisor of $3x↑6 +
x↑5 + 4x↑4 + 4x↑3 + 3x↑2 + 4x + 2$ and its ``reverse'' $2x↑6
+ 4x↑5 + 3x↑4 + 4x↑3 + 4x↑2 + x + 3$, modulo 7?

\trexno 3. [M25] Show that Euclid's algorithm for polynomials
over a field $S$ can be extended to find polynomials $U(x)$ and
$V(x)$ over $S$ such that
$$u(x)V(x) + U(x)v(x) = \gcd\biglp u(x), v(x)\bigrp .$$
(Cf.\ Algorithm 4.5.2X.)\xskip What are the degrees of
the polynomials $U(x)$ and $V(x)$ that are computed by this
extended algorithm? Prove that if $S$ is the field of rational
numbers, and if $u(x) = x↑m - 1$ and $v(x) = x↑n - 1$, then
the extended algorithm yields polynomials $U(x)$ and $V(x)$
having {\sl integer} coefficients. Find $U(x)$ and $V(x)$ when
$u(x) = x↑{21} - 1$ and $v(x) = x↑{13} - 1$.

\trexno 4. [M30] Let $p$ be prime, and suppose that Euclid's algorithm
applied to the polynomials $u(x)$ and $v(x)$ modulo $p$ yields
a sequence of polynomials having respective degrees $m$, $n$, $n↓1$,
$\ldotss$, $n↓t$, $-∞$, where $m =\hjust{deg}(u)$, $n =\hjust{deg}(v)$, and $n↓t
≥ 0$. Assume that $m ≥ n$. If $u(x)$ and $v(x)$ are monic polynomials,
independently and uniformly distributed over all the $p↑{m+n}$
pairs of monic polynomials having respective degrees $m$ and
$n$, what are the average values of the three quantities $t$, $n↓1
+\cdots + n↓t$, $(n - n↓1)n↓1 +\cdots +
(n↓{t-1} - n↓t)n↓t$, as functions of $m, n$, and $p$?\xskip (These
three quantities are the fundamental factors in the running
time of Euclid's algorithm applied to polynomials modulo $p$,
assuming that division is done by Algorithm D.)\xskip[{\sl Hint:}
Show that $u(x) \mod v(x)$ is uniformly distributed and
independent of $v(x)$.]

\exno 5. [M22] What is the probability that $u(x)$ and $v(x)$
are relatively prime modulo $p$, if $u(x)$ and $v(x)$ are independently
and uniformly distributed monic polynomials of degree\penalty999\ $n$?

\exno 6. [M23] We have seen that Euclid's Algorithm 4.5.2A for
integers can be directly adapted to an algorithm for the greatest
common divisor of polynomials. Can the ``binary gcd algorithm,''
Algorithm 4.5.2B\null, be adapted in an analogous way to an algorithm
that applies to polynomials?

\exno 7. [M10] What are the units in the domain of all polynomials
over a unique factorization domain $S?$
%folio 535 galley 8 (C) Addison-Wesley 1978	*
\def\\#1({\mathop{\hjust{#1}}(}\def\+#1\biglp{\mathop{\hjust{#1}}\biglp}
\trexno 8. [M22] Show that if a polynomial with integer coefficients is
irreducible over the domain of integers, it is irreducible when considered as
a polynomial over the field of rational numbers.

\exno 9. [M25] Let $u(x)$ and
$v(x)$ be primitive polynomials over a unique factorization
domain $S$. Prove that $u(x)$ and $v(x)$ are relatively prime
if and only if there are polynomials $U(x)$ and $V(x)$ over $S$ such
that $u(x)V(x) + U(x)v(x)$ is a polynomial of degree zero.\xskip [{\sl
Hint:} Extend Algorithm E\null, as Algorithm 4.5.2E is extended
in exercise 3.]

\exno 10. [M28] Prove that the polynomials over a unique factorization
domain form a unique factorization domain.\xskip [{\sl Hint:}
Use the result of exercise 9 to help show that there is at
most one kind of factorization possible.]

\exno 11. [M22] What row names would have appeared in Table
1 if the sequence of degrees had been 9, 6, 5, 2, $-∞$ instead
of 8, 6, 4, 2, 1, 0?

\trexno 12. [M24] Let $u↓1(x)$, $u↓2(x)$, $u↓3(x)$, $\ldots$ be a sequence
of polynomials obtained during a run of Algorithm C.\xskip``Sylvester's matrix''
is the square matrix formed from rows $A↓{n↓2-1}$ through
$A↓0$ and $B↓{n↓1-1}$ through $B↓0$ (in a notation analogous
to that of Table 1). Show that if $u↓1(x)$ and $u↓2(x)$ have
a common factor of positive degree, then the determinant of
Sylvester's matrix is zero; conversely, given that deg$(u↓k)
= 0$ for some $k$, show that the determinant of Sylvester's
matrix is nonzero by deriving a formula for its absolute value
in terms of $\lscr(u↓j)$ and deg$(u↓j)$, $1 ≤ j ≤ k$.

\exno 13. [M22] Show that the leading coefficient $\lscr$ of the
primitive part of $\gcd\biglp u(x), v(x)\bigrp$ enters into Algorithm C's
polynomial sequence as shown in (27), when $\delta↓1 = \delta↓2 =\cdots
 = \delta↓{k-1} = 1$. What is the behavior for general $\delta↓j$?

\exno 14. [M29] Let $r(x)$ be the pseudo-remainder of $u(x)$
pseudo-divided by $v(x)$. If $\\deg(u) ≥\\deg(v) + 2$ and $\\deg(v)
≥\\deg(r) + 2$, show that $r(x)$ is a multiple of $\lscr(v)$.

\exno 15. [M26] Prove Hadamard's inequality (25).\xskip [{\sl Hint:}
Consider the matrix $AA↑T$.]

\exno 16. [HM22] Let $f(x↓1, \ldotss , x↓n)$ be a multivariate
polynomial with real coefficients not all zero, and let $a↓N$
be the number of solutions to the equation $f(x↓1, \ldotss ,
x↓n) = 0$ such that $|x↓1| ≤ N$, $\ldotss$, $|x↓n| ≤ N$, and such that each
$x↓j$ is an integer. Prove that
$$\lim↓{N→∞} a↓N/(2N + 1)↑n = 0.$$

\exno 17. [M32] ({\sl P. M. Cohn's algorithm
for division of string polynomials.})\xskip Let $A$ be an ``alphabet,''
i.e., a set of symbols.\xskip A {\sl string} $α$ on $A$ is a sequence
of $n ≥ 0$ symbols, $α = a↓1 \ldotsm a↓n$, where each $a↓j$ is
in $A$. The length of $α$, denoted by $|α|$, is the number $n$
of symbols.\xskip A {\sl string polynomial} on $A$ is a finite sum
$U = \sum ↓k r↓k\,α↓k$, where each $r↓k$ is a nonzero rational
number and each $α↓k$ is a string on $A$. The {\sl degree} of
$U$, deg$(U)$, is defined to be $-∞$ if $U = 0$ (i.e., if the
sum is empty), otherwise $\\deg(u)=\max|α↓k|$. The sum and product
of string polynomials are defined in an obvious manner, e.g.,
$(\sum ↓j r↓jα↓j)(\sum ↓k s↓kβ↓k) = \sum ↓{j,k} r↓js↓kα↓jβ↓k$,
where the product of two strings is obtained by simply juxtaposing
them. For example, if $A = \{a, b\}$, $U = ab + ba - 2a - 2b$, and
$V = a + b - 1$, then deg$(U) = 2$, deg$(V) = 1$, $V↑2 = aa + ab
+ ba + bb - 2a - 2b + 1$, and $V↑2 - U = aa + bb + 1$. Clearly,
$\\deg(UV) =\\deg(U) +\\deg(V)$, and $\\deg(U + V) ≤ \max\biglp\\deg(U),
\\deg(V)\bigrp $, with equality in the latter formula if $\\deg(U)
≠\\deg(V)$.\xskip (String polynomials may be regarded as ordinary
multivariate polynomials over the field of rational numbers,
except that the variables are {\sl not commutative} under multiplication.
In the conventional language of pure mathematics, the set of
string polynomials with the operations defined here is the ``free
associative algebra'' generated by $A$ over the rationals.)

\yskip\hang\textindent{a)}Let $Q↓1$, $Q↓2$, $U$, $V$ be string polynomials
with $\\deg(U) ≥\\deg(V)$ and such that $\\deg(Q↓1U - Q↓2V) <\\deg(Q↓1U)$.
Give an algorithm to find a string polynomial $Q$ such that
$\\deg(U - QV) <\\deg(U)$.\xskip $\biglp$Thus if we are given $U$ and $V$
such that $Q↓1U = Q↓2V + R$ and $\\deg(R) <\\deg(Q↓1U)$, for
some $Q↓1$ and $Q↓2$, then there is a solution to these conditions
with $Q↓1 = 1$.$\bigrp$

\hang\textindent{b)}Given that $U$ and $V$ are string polynomials
with $\\deg(V) >\\deg(Q↓1U - Q↓2V)$ for some $Q↓1$ and $Q↓2$,
show that the result of (a) can be improved to find a quotient
$Q$ such that $U = QV + R$, $\\deg(R) <\\deg(V)$.\xskip $\biglp$This is the
analog of (1) for string polynomials; part (a) showed that we
can make $\\deg(R) <\\deg(U)$, under weaker hypotheses.$\bigrp$

\hang\textindent{c)}A ``homogeneous'' polynomial is one whose terms
all have the same degree (length). If $U↓1$, $U↓2$, $V↓1$,
$V↓2$ are homogeneous string polynomials with $U↓1V↓1 = U↓2V↓2$
and $\\deg(V↓1) ≥\\deg(V↓2)$, show that there is a homogeneous
string polynomial $U$ such that $U↓2 = U↓1U$ and $V↓1 = UV↓2$.

\hang\textindent{d)}Given that $U$ and $V$ are homogeneous string
polynomials with $UV = VU$, prove that there is a homogeneous
string polynomial $W$ such that $U = rW↑m$, $V = sW↑n$ for some
integers $m$, $n$ and rational numbers $r$, $s$. Give an algorithm
to compute such a $W$ having the largest possible degree.\xskip (This
algorithm is of interest, for example, when $U = α$ and $V =
β$ are strings satisfying $αβ = βα$; then $W$ is simply a string
$\gamma $. When $U = x↑m$ and $V = x↑n$, the solution of largest
degree is $W = x↑{\gcd(m,n)}$, so this algorithm includes a
gcd algorithm for integers as a special case.)

\trexno 18. [M24] ({\sl Euclidean algorithm for string polynomials.})\xskip
Let $V↓1$ and $V↓2$ be string polynomials, not both zero, having
a ``common left multiple.''\xskip(This means that there exist string polynomials
$U↓1$ and $U↓2$, not both zero, such that $U↓1V↓1 = U↓2V↓2$.)\xskip The purpose
of this exercise is to find an algorithm to compute their ``greatest
common right divisor'' gcrd$(V↓1, V↓2)$ as well as their ``least
common left multiple'' lclm$(V↓1, V↓2)$. The latter quantities
are defined as follows:\xskip gcrd$(V↓1, V↓2)$ is a common right divisor
of $V↓1$ and $V↓2$ (that is, $V↓1 = W↓1\\gcrd(V↓1, V↓2)$ and
$V↓2 = W↓2\\gcrd(V↓1, V↓2)$ for some $W↓1$ and $W↓2$), and any common
right divisor of $V↓1$ and $V↓2$ is a right divisor of gcrd$(V↓1,
V↓2)$; lclm$(V↓1, V↓2) = Z↓1V↓1 = Z↓2V↓2$ for some $Z↓1$ and $Z↓2$,
and any common left multiple of $V↓1$ and $V↓2$ is a left multiple
of lclm$(V↓1, V↓2)$.

For example, let $U↓1 = abbbab + abbab - bbab +
ab - 1$, $V↓1 = babab + abab + ab - b$; $U↓2 = abb + ab - b$, $V↓2
= babbabab + bababab + babab + abab - babb - 1$. Then we have
$U↓1V↓1 = U↓2V↓2 = abbbabbabab + abbabbabab + abbbababab + abbababab
- bbabbabab + abbbabab - bbababab + 2abbabab - abbbabb + ababab
- abbabb - bbabab - babab + bbabb - abb - ab + b$. For these
string polynomials it can be shown that gcrd$(V↓1, V↓2) = ab
+ 1$, and lclm$(V↓1, V↓2) = U↓1V↓1$.

The division algorithm of exercise 17 may be restated
thus: If $V↓1$ and $V↓2$ are string polynomials, with $V↓2 ≠
0$, and if $U↓1 ≠ 0$ and $U↓2$ satisfy the equation $U↓1V↓1
= U↓2V↓2$, then there exist string polynomials $Q$ and $R$ such
that $V↓1 = QV↓2 + R$, $\\deg(R) <\\deg(V↓2)$.\xskip{\sl Note:} It
follows readily that $Q$ and $R$ are uniquely determined, they
do not depend on $U↓1$ and $U↓2$; furthermore the result is
right-left symmetric in the sense that
$$U↓2 = U↓1Q + R↑\prime \qquad\hjust{where }\\deg(R↑\prime )
=\\deg(U↓1)-\\deg(V↓2) +\\deg(R) <\\deg(U↓1).$$

Show that this division algorithm can be
extended to an algorithm that computes lclm$(V↓1, V↓2)$ and
gcrd$(V↓1, V↓2)$, and, in fact, the extended algorithm finds string polynomials
$Z↓1$ and $Z↓2$ such that $Z↓1V↓1 + Z↓2V↓2 =\\gcrd(V↓1, V↓2)$.\xskip [{\sl Hint:}
Use auxiliary variables $u↓1$, $u↓2$, $v↓1$, $v↓2$, $w↓1$, $w↓2$, $w↑\prime↓{1}$,
$w↑\prime↓{2}$, $z↓1$, $z↓2$, $z↑\prime↓{1}$, $z↑\prime↓{2}$,
whose values are string polynomials; start by setting $u↓1 ←
U↓1$, $u↓2 ← U↓2$, $v↓1 ← V↓1$, $v↓2 ← V↓2$, and throughout the algorithm
maintain the conditions
$$\baselineskip14pt
\eqalign{U↓1w↓1 + U↓2w↓2 ⊗= u↓1,\cr
U↓1w↑\prime↓{1} + U↓2w↑\prime↓{2} ⊗= u↓2,\cr
u↓1z↓1 - u↓2z↑\prime↓{1} ⊗= (-1)↑nU↓1,\cr
-u↓1z↓2 + u↓2z↑\prime↓{2} ⊗= (-1)↑nU↓2,\cr}\qquad\eqalign{
z↓1V↓1 + z↓2V↓2⊗= v↓1,\cr
z↑\prime↓{1}V↓1 + z↑\prime↓{2}V↓2 ⊗= v↓2,\cr
w↓1v↓1 - w↑\prime↓{1}v↓2 ⊗= (-1)↑nV↓1,\cr
-w↓2v↓1 + w↑\prime↓{2}v↓2 ⊗= (-1)↑nV↓2\cr}$$
at the $n$th iteration. This might be regarded as the ``ultimate'' extension
of Euclid's algorithm.]

\exno 19. [M39] ({\sl Common divisors of square matrices.})\xskip Exercise
18 shows that the concept of greatest common right divisor can
be meaningful when multiplication is not commutative. Prove
that any two $n \times n$ matrices $A$ and $B$ of integers have
a greatest common right matrix divisor $D$.\xskip [{\sl Suggestion:}
Design an algorithm whose inputs are $A$ and $B$, and whose
outputs are integer matrices $P$, $Q$, $X$, $Y$, where $A = PD$, $B
= QD$, $D = XA + YB$.]\xskip Find a greatest common right divisor of
$({1\atop 3}\,{2\atop 4})$ and $({4\atop 2}\,{3\atop 1})$.

\exno 20. [M40] Investigate the accuracy of Euclid's algorithm:
What can be said about
calculation of the greatest common divisor of polynomials whose
coefficients are floating-point numbers?

\exno 21. [M25] Prove that the computation
time required by Algorithm C to compute the gcd of two $n$th
degree polynomials over the integers is $O\biglp n↑4(\log Nn)↑2\bigrp
$, if the coefficients of the given polynomials are bounded
by $N$ in absolute value.

\exno 22. [M23] Prove Sturm's theorem.\xskip
[{\sl Hint:} Some sign sequences are impossible.]

\exno 23. [M22] Prove that if $u(x)$ in (28) has deg$(u)$ real
roots, then $\\deg(u↓{j+1}) =\\deg(u↓j) - 1$ for $0 ≤ j ≤ k$.

\exno 24. [M21] Show that (19) simplifies to (20) and (23) simplifies to (24).

\exno 25. [M24] (W. S. Brown.)\xskip Prove that all the polynomials $u↓j(x)$
in (16) for $j≥3$ are multiples of $\gcd\biglp\lscr(u),\lscr(v)\bigrp$,
and explain how to improve Algorithm C accordingly.

\runningrighthead{FACTORIZATION OF POLYNOMIALS}
\section{4.6.2}
\sectionskip
\sectionbegin{\star4.6.2. Factorization of Polynomials}
Let us now consider
the problem of {\sl factoring} polynomials, not merely finding
the greatest common divisor of two or more of them.

\subsectionbegin{Factoring modulo $\spose{$p$}\hskip.25pt p$} As in the
case of integer numbers (Sections 4.5.2, 4.5.4), the problem
of factoring seems to be more difficult than finding the greatest
common divisor. But factorization of polynomials modulo a prime
integer $p$ is not as hard to do as we might expect. It is much
easier to find the factors of an arbitrary polynomial of degree
$n$, modulo 2, than to use any known method to find the factors
of an arbitrary $n$-bit binary number. This surprising situation
is a consequence of an important factorization algorithm discovered
in 1967 by Elwyn R. Berlekamp [{\sl Bell System Technical J.
\bf 46} (1967), 1853--1859].

Let $p$ be a prime number; all arithmetic on polynomials
in the following discussion will be done modulo $p$. Suppose
that someone has given us a polynomial $u(x)$, whose coefficients
are chosen from the set $\{0, 1, \ldotss , p - 1\}$; we may assume
that $u(x)$ is monic. Our goal is to express $u(x)$ in the form
$$u(x) = p↓1(x)↑{e↓1} \ldotss p↓r(x)↑{e↓r},\eqno (1)$$
where $p↓1(x)$, $\ldotss$, $p↓r(x)$ are distinct, monic,
irreducible polynomials.
%folio 539 galley 9 Almost total loss. (C) Addison-Wesley 1978	*
\def\\#1({\mathop{\hjust{#1}}(}\def\Modulo#1){\penalty0\;\;\biglp\char'155
\char'157\char'144\char'165\char'154\char'157\,\,#1)\bigrp}
As a first step, we can use a standard technique
to determine whether any of the exponents $e↓1$, $\ldotss$, $e↓r$ are greater
than unity. If
$$u(x) = u↓nx↑n +\cdots + u↓0 = v(x)↑2w(x),\eqno(2)$$
then its ``derivative'' formed in the usual way
(but modulo $p$) is
$$u↑\prime (x) = nu↓nx↑{n-1} +\cdots + u↓1 = 2v(x)v↑\prime(x)w(x)+v(x)↑2w↑\prime(x),
\eqno (3)$$
and this is a multiple of the squared factor $v(x)$.
Therefore our first step in factoring $u(x)$ is to form
$$\gcd\biglp u(x), u↑\prime (x)\bigrp = d(x).\eqno (4)$$
If $d(x)$ is equal to 1, we know that $u(x)$
is ``squarefree,'' the product of distinct primes $p↓1(x) \ldotsm
p↓r(x)$. If $d(x)$ is not equal to 1 and $d(x) ≠ u(x)$, then
$d(x)$ is a proper factor of $u(x)$; so the process can be completed
by factoring $d(x)$ and $u(x)/d(x)$ separately. Finally, if
$d(x) = u(x)$, we must have $u↑\prime (x) = 0$; hence the coefficient
$u↓k$ of $x↑k$ is nonzero only when $k$ is a multiple of $p$.
This means that $u(x)$ can be written as a polynomial of the
form $v(x↑p)$, and in such a case we have
$$u(x) = v(x↑p) = \biglp v(x)\bigrp ↑p;\eqno (5)$$
the factorization process can be completed by finding
the irreducible factors of $v(x)$ and raising them to the $p$th
power.

Identity (5) may appear somewhat strange to the
reader, and it is an important fact that is basic to Berlekamp's
algorithm. We can prove it as follows: If $v↓1(x)$ and $v↓2(x)$
are any polynomials modulo $p$, then
$$\baselineskip16pt\eqalign{
\biglp v↓1(x)v↓2(x)\bigrp↑p⊗=v↓1(x)↑pv↓2(x)↑p,\cr
\noalign{\vskip2pt}
\biglp v↓1(x)+v↓2(x)\bigrp↑p⊗=\textstyle v↓1(x)↑p+{p\choose1}v↓1(x)↑pv↓2(x)+\cdots
+{p\choose p-1}v↓1(x)v↓2(x)↑{p-1}+v↓2(x)↑p\cr
⊗=v↓1(x)↑p+v↓2(x)↑p,\cr}$$
since the binomial coefficients $p\choose1$, $\ldotss$, $p\choose p-1$ are all
multiples of $p$.\xskip Furthermore if $a$ is any integer, $a↑p≡a\modulo p$.
Therefore when $v(x)=v↓mx↑m+v↓{m-1}x↑{m-1}+\cdots+v↓0$, we find that
$$\baselineskip15pt\eqalign{
v(x)↑p ⊗= (v↓mx↑m)↑p + (v↓{m-1}x↑{m-1})↑p +
\cdots + (v↓0)↑p\cr
⊗= v↓mx↑{mp} + v↓{m-1}x↑{(m-1)p} +\cdots +
v↓0\; =\; v(x↑p).\cr}$$ This proves (5).

The above remarks show that the problem of factoring
a polynomial reduces to the problem of factoring a squarefree
polynomial. Let us therefore assume that
$$u(x)=p↓1(x)p↓2(x)\ldotsm p↓r(x)\eqno(6)$$
is the product of distinct primes. How can we be clever enough to discover the
$p↓j(x)$'s when only $u(x)$ is given? Berlekamp's idea is to make use of the
Chinese remainder theorem, which is valid for polynomials just as it is valid
for integers (see exercise 3). If $(s↓1,s↓2,\ldotss,s↓r)$ is any $r$-tuple
of integers mod $p$, the Chinese remainder theorem implies that {\sl there is
a unique polynomial $v(x)$ such that}
$$\baselineskip15pt\cpile{
v(x)≡s↓1\Modulo p↓1(x),\quad\ldotss,\quad v(x)≡s↓r\Modulo p↓r(x),\cr
\\deg(v)<\\deg(p↓1)+\\deg(p↓2)+\cdots+\\deg(p↓r)=\\deg(u).\cr}\eqno(7)$$
The notation $g(x)≡h(x)\Modulo f(x)$ that appears here is the same as ``$g(x)≡h(x)$
$\biglp$modulo $f(x)$ and $p\bigrp$'' in exercise 3.2.2--11,
since we are considering polynomial arithmetic modulo $p$.
The polynomial $v(x)$ in (7) gives us a way to get at the factors of $u(x)$,
for if $r≥2$ and $s↓1≠s↓2$, we will have $\gcd\biglp u(x),v(x)-s↓1\bigrp$
divisible by $p↓1(x)$ but not by $p↓2(x)$.

Since this observation shows that we can get information about the factors of
$u(x)$ from appropriate solutions $v(x)$ of (7), let us analyze (7) more
closely. In the first place we can observe that the polynomial $v(x)$
satisfies the condition $v(x)↑p≡s↓j↑p=s↓j≡v(x)\Modulo p↓j(x)$ for $1≤j≤r$,
therefore
$$v(x)↑p≡v(x)\Modulo u(x),\qquad \\deg(v)<\\deg(u).\eqno(8)$$
In the second place we have the basic polynomial identity
$$x↑p - x ≡ (x - 0)(x - 1) \ldotsm \biglp x - (p - 1)\bigrp\quad\modulo p\eqno (9)$$
(see exercise 6); hence
$$v(x)↑p - v(x) = \biglp v(x) - 0\bigrp\biglp v(x) -
1\bigrp \ldotsm \biglp v(x) - (p - 1)\bigrp \eqno (10)$$
is an identity for any polynomial $v(x)$, when
we are working modulo $p$. If $v(x)$ satisfies (8), it follows
that $u(x)$ divides the left-hand side of (10), so every irreducible
factor of $u(x)$ must divide one of the $p$ relatively prime
factors of the right-hand side of (10). In other words, {\sl
all} solutions of (8) must have the form of (7), for some $s↓1$,
$s↓2$, $\ldotss$, $s↓r$; {\sl there are exactly $p↑r$ solutions of $(8)$}.
%folio 541 galley 10 (C) Addison-Wesley 1978	*
\def\\#1({\mathop{\hjust{#1}}(}\def\Modulo#1){\penalty0\;\;\biglp\char'155
\char'157\char'144\char'165\char'154\char'157\,\,#1)\bigrp}

The solutions $v(x)$ to congruence (8) therefore
provide a key to the factorization of $u(x)$. It may seem harder
to find all solutions to (8) than to factor $u(x)$ in the first
place, but in fact this is not true, since the set of solutions
to (8) is closed under addition. Let deg$(u) = n$; we can construct
the $n \times n$ matrix
$$Q=\left(\,\vcenter{\halign{$\ctr{#}$⊗\quad$\ctr{#}$⊗\quad$\ctr{#}$⊗\quad
$\ctr{#}$\cr
q↓{0,0}⊗q↓{0,1}⊗\ldots⊗q↓{0,n-1}\cr
\vdots⊗\vdots⊗⊗\vdots\cr
q↓{n-1,0}⊗q↓{n-1,1}⊗\ldots ⊗q↓{n-1,n-1}\cr}}\,\right)\eqno(11)$$
where
$$x↑{pk} ≡ q↓{k,n-1}x↑{n-1} +\cdots + q↓{k,1}x +
q↓{k,0}\;\Modulo u(x).\eqno (12)$$
Then $v(x) = v↓{n-1}x↑{n-1} +\cdots
+ v↓1x + v↓0$ is a solution to (8) if and only if
$$(v↓0, v↓1, \ldotss , v↓{n-1})Q = (v↓0, v↓1, \ldotss , v↓{n-1});\eqno
(13)$$
for the latter equation holds if and only if
$$\chop to 12pt{v(x) = \sum ↓{j} v↓j\,x↑j = \sum ↓{j} \sum ↓{k} v↓k\,q↓{k,j}\,x↑j
≡ \sum ↓{k} v↓k\,x↑{pk} = v(x↑p)\Modulo u(x).}$$

Berlekamp's factoring algorithm therefore proceeds
as follows:

\yskip\hang\textindent{\bf B1.}Ensure that $u(x)$ is squarefree; i.e.,
if $\gcd\biglp u(x), u↑\prime (x)\bigrp ≠ 1$, reduce
the problem of factoring $u(x)$, as stated earlier in this section.

\yskip\hang\textindent{\bf B2.}Form the matrix $Q$ defined by (11) and (12). This
can be done in one of two ways, depending on whether or not
$p$ is very large, as explained below.

\yskip\hang\textindent{\bf B3.}``Triangularize'' the matrix $Q - I$, where $I
= (\delta ↓{ij})$ is the $n \times n$ identity matrix, finding
its rank $n - r$ and finding linearly independent vectors $v↑{[1]}$,
$\ldotss$, $v↑{[r]}$ such that $v↑{[j]}(Q - I) = (0, 0, \ldotss
, 0)$ for $1 ≤ j ≤ r$.\xskip $\biglp$The first vector $v↑{[1]}$ may always
be taken as $(1, 0, \ldotss , 0)$, representing the trivial solution
$v↑{[1]}(x) = 1$ to (8). The ``triangularization'' needed in this step can
be done using appropriate column operations, as explained in
Algorithm N below.$\bigrp$\xskip{\sl At this point, $r$ is the number of irreducible
factors of $u(x)$}, because the solutions to (8) are the $p↑r$
polynomials corresponding to the vectors $t↓1v↑{[1]} +
\cdots + t↓rv↑{[r]}$ for all choices of integers $0 ≤ t↓1,
\ldotss, t↓r < p$. Therefore if $r = 1$ we know that $u(x)$
is irreducible, and the procedure terminates.

\yskip\hang\textindent{\bf B4.}Calculate $\gcd\biglp u(x), v↑{[2]}(x) - s\bigrp$
for $0 ≤ s < p$, where $v↑{[2]}(x)$ is the polynomial
represented by vector $v↑{[2]}$. The result will be a nontrivial
factorization of $u(x)$, because $v↑{[2]}(x) - s$ is nonzero
and has degree less than deg($u)$, and by exercise 7 we have
$$u(x) = \prod ↓{0≤s<p} \gcd\biglp v(x) - s,\, u(x)\bigrp \eqno(14)$$
whenever $v(x)$ satisfies (8).

\hangindent 19pt after 0 If the use of $v↑{[2]}(x)$ does not succeed
in splitting $u(x)$ into $r$ factors, further factors can be
obtained by calculating $\gcd\biglp v↑{[k]}(x) - s,\, w(x)\bigrp$
for $0 ≤ s < p$ and all factors $w(x)$ found so far, for $k
= 3$, 4, $\ldotss $, until $r$ factors are obtained.\xskip $\biglp$If we choose
$s↓i ≠ s↓j$ in (7), we obtain a solution $v(x)$ to (8) that
distinguishes $p↓i(x)$ from $p↓j(x)$; some $v↑{[k]}(x) - s$
will be divisible by $p↓i(x)$ and not by $p↓j(x)$, so this procedure
will eventually find all of the factors.$\bigrp$\quad\blackslug

\yyskip As an example of this procedure,
let us now determine the factorization of
$$u(x) = x↑8 + x↑6 + 10x↑4 + 10x↑3 + 8x↑2 + 2x + 8\eqno (15)$$
modulo 13.\xskip (This polynomial appears in several
of the examples in Section 4.6.1.)\xskip A quick calculation using
Algorithm 4.6.1E shows that $\gcd\biglp u(x), u↑\prime (x)\bigrp
= 1$; therefore $u(x)$ is squarefree, and we turn to step B2.
Step B2 involves calculating the $Q$ matrix, which in this case
is an $8 \times 8$ array. The first row of $Q$ is always $(1, 0,
0, \ldotss , 0)$, representing the polynomial $x↑0\mod u(x)
= 1$. The second row represents $x↑{13}\mod u(x)$, and, in
general, $x↑k\mod u(x)$ may readily be determined as follows
(for relatively small values of $k$): If
$$u(x) = x↑n + u↓{n-1}x↑{n-1} +\cdots+ u↓1x + u↓0$$
and if
$$x↑k ≡ a↓{k,n-1}x↑{n-1} +\cdots + a↓{k,1}x + a↓{k,0}\Modulo u(x),$$
then
$$\baselineskip15pt\eqalign{x↑{k+1}⊗ ≡ a↓{k,n-1}x↑n +\cdots + a↓{k,1}x↑2
+ a↓{k,0}x\cr ⊗≡ a↓{k,n-1}(-u↓{n-1}x↑{n-1} -\cdots
- u↓1x - u↓0) + a↓{k,n-2}x↑{n-1} +\cdots +
a↓{k,0}x\cr
⊗= a↓{k+1,n-1}x↑{n-1} +\cdots + a↓{k+1,1}x+ a↓{k+1,0},\cr}$$
where
$$a↓{k+1,j} = a↓{k,j-1} - a↓{k,n-1}u↓j.\eqno (16)$$
In this formula $a↓{k,-1}$ is treated as zero,
so that $a↓{k+1,0} = -a↓{k,n-1}u↓0$. The simple ``shift register''
recurrence (16) makes it easy to calculate $x↑1$, $x↑2$, $x↑3$, $\ldots$
mod $u(x)$. Inside a computer, this calculation would of course
be done by keeping a one-dimensional array $(a↓{n-1}, \ldotss
, a↓1, a↓0)$ and repeatedly setting $t ← a↓{n-1}$, $a↓{n-1} ←
(a↓{n-2} - tu↓{n-1}) \mod p$, $\ldotss$, $a↓1 ← (a↓0 - tu↓1)\mod
p$, $a↓0 ← (-tu↓0)\mod p$.\xskip (We have seen similar procedures
in connection with random-number generation; cf.\ 3.2.2--10.)\xskip
For our example polynomial $u(x)$ in (15), we obtain the following
sequence of coefficients of $x↑k \mod u(x)$, using arithmetic
modulo 13:
$$\def\\#1{\hskip-10pt$#1$\hskip-10pt\hfill}
\vjust{\:b
\halign{\hfill#⊗\qquad\hfill#⊗\qquad\hfill#⊗\qquad\hfill#⊗\qquad
\hfill#⊗\qquad\hfill#⊗\qquad\hfill#⊗\qquad\hfill#⊗\qquad\hfill#\cr
$k$⊗\\{a↓{k,7}}⊗\\{a↓{k,6}}⊗\\{a↓{k,5}}⊗\\{a↓{k,4}}⊗\\{a↓{k,3}}⊗
\\{a↓{k,2}}⊗\\{a↓{k,1}}⊗\\{a↓{k,0}}\cr
\noalign{\vskip 2pt}
0⊗0⊗0⊗0⊗0⊗0⊗0⊗0⊗1\cr
1⊗0⊗0⊗0⊗0⊗0⊗0⊗1⊗0\cr
2⊗0⊗0⊗0⊗0⊗0⊗1⊗0⊗0\cr
3⊗0⊗0⊗0⊗0⊗1⊗0⊗0⊗0\cr
4⊗0⊗0⊗0⊗1⊗0⊗0⊗0⊗0\cr
5⊗0⊗0⊗1⊗0⊗0⊗0⊗0⊗0\cr
6⊗0⊗1⊗0⊗0⊗0⊗0⊗0⊗0\cr
7⊗1⊗0⊗0⊗0⊗0⊗0⊗0⊗0\cr
8⊗0⊗12⊗0⊗3⊗3⊗5⊗11⊗5\cr
9⊗12⊗0⊗3⊗3⊗5⊗11⊗5⊗0\cr
10⊗0⊗4⊗3⊗2⊗8⊗0⊗2⊗8\cr
11⊗4⊗3⊗2⊗8⊗0⊗2⊗8⊗0\cr
12⊗3⊗11⊗8⊗12⊗1⊗2⊗5⊗7\cr
13⊗11⊗5⊗12⊗10⊗11⊗7⊗1⊗2\cr}}$$
Therefore the second row of $Q$ is $(2, 1, 7,
11, 10, 12, 5, 11)$. Similarly we may determine $x↑{26}\mod
u(x)$, $\ldotss$, $x↑{91}\mod u(x)$, and we find that
$$\eqalign{Q⊗=\left(\,\vcenter{\halign{\hfill#⊗\quad\hfill#⊗\quad\hfill#⊗\quad
\hfill#⊗\quad\hfill#⊗\quad\hfill#⊗\quad\hfill#⊗\quad\hfill#\cr
1⊗0⊗0⊗0⊗0⊗0⊗0⊗0\cr
2⊗1⊗7⊗11⊗10⊗12⊗5⊗11\cr
3⊗6⊗4⊗3⊗0⊗4⊗7⊗2\cr
4⊗3⊗6⊗5⊗1⊗6⊗2⊗3\cr
2⊗11⊗8⊗8⊗3⊗1⊗3⊗11\cr
6⊗11⊗8⊗6⊗2⊗7⊗10⊗9\cr
5⊗11⊗7⊗10⊗0⊗11⊗7⊗12\cr
3⊗3⊗12⊗5⊗0⊗11⊗9⊗12\cr}}\,\right),\cr
\noalign{\vskip9pt}
Q-I⊗=\left(\,\vcenter{\halign{\hfill#⊗\quad\hfill#⊗\quad\hfill#⊗\quad
\hfill#⊗\quad\hfill#⊗\quad\hfill#⊗\quad\hfill#⊗\quad\hfill#\cr
0⊗0⊗0⊗0⊗0⊗0⊗0⊗0\cr
2⊗0⊗7⊗11⊗10⊗12⊗5⊗11\cr
3⊗6⊗3⊗3⊗0⊗4⊗7⊗2\cr
4⊗3⊗6⊗4⊗1⊗6⊗2⊗3\cr
2⊗11⊗8⊗8⊗2⊗1⊗3⊗11\cr
6⊗11⊗8⊗6⊗2⊗6⊗10⊗9\cr
5⊗11⊗7⊗10⊗0⊗11⊗6⊗12\cr
3⊗3⊗12⊗5⊗0⊗11⊗9⊗11\cr}}\,\right).\cr}\eqno(17)$$
%folio 543 galley 11 (C) Addison-Wesley 1978	*
\def\\#1({\mathop{\hjust{#1}}(}\def\Modulo#1){\penalty0\;\;\biglp\char'155
\char'157\char'144\char'165\char'154\char'157\,\,#1)\bigrp}
\def\circle#1{\hjust to 10pt{#1\hskip-10ptminus10pt
\raise 6.944pt\hjust{\:@\char'141}\hskip0ptminus10pt}}
That finishes step B2; the next step of Berlekamp's procedure requires
finding the ``null space'' of $Q - I$. In general, suppose that
$A$ is an $n \times n$ matrix over a field, whose rank $n -
r$ is to be determined; suppose further that we wish to determine
linearly independent vectors $v↑{[1]}$, $v↑{[2]}$, $\ldotss$, $v↑{[r]}$
such that $v↑{[1]}A = v↑{[2]}A = \cdots =v↑{[r]}A = (0, \ldotss
, 0)$. An algorithm for this calculation can be based on the
observation that any column of $A$ may be multiplied by a nonzero
quantity, and any multiple of one of its columns may be added
to a different column, without changing the rank or the vectors
$v↑{[1]}, \ldotss , v↑{[r]}$.\xskip (These transformations amount to
replacing $A$ by $AB$, where $B$ is a nonsigular matrix.)\xskip The
following well-known ``triangularization'' procedure may therefore
be used.

\algbegin Algorithm N (Null space algorithm).
Let $A$ be an $n \times n$ matrix, whose elements
$a↓{ij}$ belong to a field and have subscripts in the range
$0 ≤ i, j < n$. This algorithm outputs $r$ vectors $v↑{[1]}$,
$\ldotss$, $v↑{[r]}$, which are linearly independent over the field
and satisfy $v↑{[j]}A = (0, \ldotss , 0)$, where $n - r$ is the
rank of $A$.

\algstep N1. [Initialize.] Set $c↓0 ← c↓1
←\cdots ← c↓{n-1} ← -1$, $r ← 0$.\xskip (During the calculation
we will have $c↓j ≥ 0$ only if $a↓{c↓jj}= -1$ and all
other entries of row $c↓j$ are zero.)

\algstep N2. [Loop on $k$.] Do step N3 for $k = 0$, 1, $\ldotss$,
$n - 1$, and then terminate the algorithm.

\algstep N3. [Scan row for dependence.] If there is some $j$
in the range $0 ≤ j < n$ such that $a↓{kj} ≠ 0$ and $c↓j < 0$,
then do the following: Multiply column $j$ of $A$ by $-1/a↓{kj}$
(so that $a↓{kj}$ becomes equal to $-1$); then add $a↓{ki}$ times
column $j$ to column $i$ for all $i ≠ j$; finally set $c↓j ←
k$.\xskip (Since it is not difficult to show that $a↓{sj} = 0$ for
all $s < k$, these operations have no effect on rows 0, 1, $\ldotss$,
$k - 1$ of $A$.)

\hangindent19pt after 0 On the other hand, if there is no $j$ in
the range $0 ≤ j < n$ such that $a↓{kj} ≠ 0$ and $c↓j < 0$,
then set $r ← r + 1$ and output the vector
$$v↑{[r]} = (v↓0, v↓1, \ldotss , v↓{n-1})$$
defined by the rule
$$v↓j=\left\{\vcenter{\halign{$#,\hfill$\qquad⊗#\hfill\cr
a↓{ks}⊗if $c↓s=j≥0$;\cr 1⊗if $j=k$;\cr 0⊗otherwise.\hskip50pt\blackslug\cr}}
\right.\eqno(18)$$

\yyskip An example will reveal the mechanism
of this algorithm. Let $A$ be the matrix $Q - I$ of (17) over
the field of integers modulo 13. When $k = 0$, we output the
vector $v↑{[1]} = (1, 0, 0, 0, 0, 0, 0, 0)$. When $k = 1$, we
may take $j$ in step N3 to be either 0, 2, 3, 4, 5, 6, or 7;
the choice here is completely arbitrary, although it affects
the particular vectors that are chosen to be output by the
algorithm. For hand calculation, it is most convenient to pick
$j = 5$, since $a↓{15} = 12 = -1$ already; the column operations
of step N3 then change $A$ to the matrix
$$\left(\,\vcenter{\halign{\hjust to 10pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\!
\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\!
\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}\cr
0⊗0⊗0⊗0⊗0⊗0⊗0⊗0\cr
0⊗0⊗0⊗0⊗0⊗\circle{12}⊗0⊗0\cr
11⊗6⊗5⊗8⊗1⊗4⊗1⊗7\cr
3⊗3⊗9⊗5⊗9⊗6⊗6⊗4\cr
4⊗11⊗2⊗6⊗12⊗1⊗8⊗9\cr
5⊗11⊗11⊗7⊗10⊗6⊗1⊗10\cr
1⊗11⊗6⊗1⊗6⊗11⊗9⊗3\cr
12⊗3⊗11⊗9⊗6⊗11⊗12⊗2\cr
}}\,\right).$$
(The circled element in column ``5'', row
``1'', is used here to indicate that $c↓5 = 1$. Remember that
Algorithm N numbers the rows and columns of the matrix starting
with 0, not 1.)\xskip When $k = 2$, we may choose $j = 4$ and proceed
in a similar way, obtaining the following matrices, which all
have the same null space as $Q - I$:
$$\hjust to size{$\dispstyle{k=2\lower5pt\null\atop
\left(\,\vcenter{\halign{\hjust to 10pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\!
\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\!
\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}\cr
0⊗0⊗0⊗0⊗0⊗0⊗0⊗0\cr
0⊗0⊗0⊗0⊗0⊗\circle{12}⊗0⊗0\cr
0⊗0⊗0⊗0⊗\circle{12}⊗0⊗0⊗0\cr
8⊗1⊗3⊗11⊗4⊗9⊗10⊗6\cr
2⊗4⊗7⊗1⊗1⊗5⊗9⊗3\cr
12⊗3⊗0⊗5⊗3⊗5⊗4⊗5\cr
0⊗1⊗2⊗5⊗7⊗0⊗3⊗0\cr
11⊗6⊗7⊗0⊗7⊗0⊗6⊗12\cr
}}\,\right)}\hfill
{k=3\lower5pt\null\atop
\left(\,\vcenter{\halign{\hjust to 10pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\!
\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\!
\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}\cr
0⊗0⊗0⊗0⊗0⊗0⊗0⊗0\cr
0⊗0⊗0⊗0⊗0⊗\circle{12}⊗0⊗0\cr
0⊗0⊗0⊗0⊗\circle{12}⊗0⊗0⊗0\cr
0⊗\circle{12}⊗0⊗0⊗0⊗0⊗0⊗0\cr
9⊗9⊗8⊗9⊗11⊗8⊗8⊗5\cr
1⊗10⊗4⊗11⊗4⊗4⊗0⊗0\cr
5⊗12⊗12⊗7⊗3⊗4⊗6⊗7\cr
2⊗7⊗2⊗12⊗9⊗11⊗11⊗2\cr
}}\,\right)}$}$$

$$\hjust to size{$\dispstyle{k=4\lower5pt\null\atop
\left(\,\vcenter{\halign{\hjust to 10pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\!
\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\!
\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}\cr
0⊗0⊗0⊗0⊗0⊗0⊗0⊗0\cr
0⊗0⊗0⊗0⊗0⊗\circle{12}⊗0⊗0\cr
0⊗0⊗0⊗0⊗\circle{12}⊗0⊗0⊗0\cr
0⊗\circle{12}⊗0⊗0⊗0⊗0⊗0⊗0\cr
0⊗0⊗0⊗0⊗0⊗0⊗0⊗\circle{12}\cr
1⊗10⊗4⊗11⊗4⊗4⊗0⊗0\cr
8⊗2⊗6⊗10⊗11⊗11⊗0⊗9\cr
1⊗6⊗4⊗11⊗2⊗0⊗0⊗10\cr
}}\,\right)}\hfill
{k=5\lower5pt\null\atop
\left(\,\vcenter{\halign{\hjust to 10pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\!
\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\!
\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}\cr
0⊗0⊗0⊗0⊗0⊗0⊗0⊗0\cr
0⊗0⊗0⊗0⊗0⊗\circle{12}⊗0⊗0\cr
0⊗0⊗0⊗0⊗\circle{12}⊗0⊗0⊗0\cr
0⊗\circle{12}⊗0⊗0⊗0⊗0⊗0⊗0\cr
0⊗0⊗0⊗0⊗0⊗0⊗0⊗\circle{12}\cr
\circle{12}⊗0⊗0⊗0⊗0⊗0⊗0⊗0\cr
5⊗0⊗0⊗0⊗5⊗5⊗0⊗9\cr
12⊗9⊗0⊗0⊗11⊗9⊗0⊗10\cr
}}\,\right)}$}$$
Now every column that has no circled entry is
completely zero; so when $k = 6$ and $k = 7$ the algorithm outputs
two more vectors, namely
$$v↑{[2]} = (0, 5, 5, 0, 9, 5, 1, 0),\qquad v↑{[3]} = (0, 9,
11, 9, 10, 12, 0, 1).$$
From the form of matrix $A$ after $k = 5$, it is
evident that these vectors satisfy the equation $vA = (0, \ldotss
, 0)$. Since the computation has produced three linearly independent
vectors, $u(x)$ must have exactly three irreducible factors.
%folio 545 galley 12 (C) Addison-Wesley 1978	*
Finally we can go to step B4 of the factoring procedure.
The calculation of $\gcd\biglp u(x),\, v↑{[2]}(x) -s\bigrp$ for $s
= 0$, 1, $\ldotss$, 12, where $v↑{[2]}(x) = x↑6 + 5x↑5 + 9x↑4
+ 5x↑2 + 5x$, gives $x↑5 + 5x↑4 + 9x↑3 + 5x + 5$ as the answer
when $s = 0$,\xskip $x↑3 + 8x↑2 + 4x + 12$ when $s = 2$, and unity for
other values of $s$. Therefore $v↑{[2]}(x)$ gives us only two
of the three factors. Turning to $\gcd\biglp v↑{[3]}(x) - s,\,
x↑5 + 5x↑4 + 9x↑3 + 5x + 5\bigrp $, where $v↑{[3]}(x) = x↑7 + 12x↑5
+ 10x↑4 + 9x↑3 + 11x↑2 + 9x$, we obtain the value $x↑4 + 2x↑3
+ 3x↑2 + 4x + 6$ when $s = 6$,\xskip $x + 3$ when $s = 8$, and unity
otherwise. Thus the complete factorization is
$$u(x) = (x↑4 + 2x↑3 + 3x↑2 + 4x + 6)(x↑3 + 8x↑2 + 4x + 12)(x
+ 3).\eqno (19)$$

Let us now estimate the running time of Berlekamp's
method when an $n$th degree polynomial is factored modulo $p$.
First assume that $p$ is relatively small, so that the four
arithmetic operations can be done modulo $p$ in essentially
a fixed length of time.\xskip (Division modulo $p$ can be converted
to multiplication, by storing a table of reciprocals; modulo
13, for example, we have ${1\over 2} = 7$, ${1\over 3} = 9$,
etc.)\xskip The computation in step B1 takes $O(n↑2)$ units of time;
step B2 takes $O(pn↑2)$. For step B3 we use Algorithm N\null, which
requires $O(n↑3)$ units of time at most. Finally, in step B4
we can observe that the calculation of $\gcd\biglp f(x), g(x)\bigrp$
by Euclid's algorithm takes $O\biglp\hjust{deg}(f)\,\hjust{deg}(g)\bigrp$
units of time; hence the calculation of $\gcd\biglp v↑{[j]}(x)
- s,\, w(x)\bigrp$ for fixed $j$ and $s$ and for all factors $w(x)$
of $u(x)$ found so far takes $O(n↑2)$ units. Step B4 therefore
requires $O(prn↑2)$ units of time at most. {\sl Berlekamp's
procedure factors an arbitrary polynomial of degree $n$}, modulo
$p$, {\sl in $O(n↑3 + prn↑2)$ steps}, when $p$ is a small prime; and
exercise 5 shows that the average number of factors, $r$, is
approximately $\ln n$. Thus the algorithm is much faster than
any known methods of factoring $n$-digit numbers in the $p$-ary
number system.

When $p$ is large, a different implementation of
Berlekamp's procedure would be used for the calculations. Division
modulo $p$ would not be done with an auxiliary table of reciprocals;
instead the method of exercise 4.5.2--15, which takes $O\biglp
(\log p)↑2\bigrp$ steps, would probably be used. Then step
B1 would take $O\biglp n↑2(\log p)↑2\bigrp$ units of time;
similarly, step B3 takes $O\biglp n↑3(\log p)↑2\bigrp $. In
step B2, we can form $x↑p\mod u(x)$ in a more efficient way
than (16) when $p$ is large: Section 4.6.3 shows that this value
can essentially be obtained by using $O(\log p)$ operations
of ``squaring $\null\mod u(x)$,'' i.e., going from $x↑k\mod u(x)$
to $x↑{2k}\mod u(x)$. The squaring operation is relatively
easy to perform if we first make an auxiliary table of $x↑m
\mod u(x)$ for $m = n$, $n + 1$, $\ldotss$, $2n -2$; if
$$x↑k \mod u(x) = c↓{n-1}x↑{n-1} +\cdots
+ c↓1x + c↓0,$$
then
$$x↑{2k} \mod u(x) = \biglp c↑{2}↓{n-1}x↑{2n-2} +\cdots
+ (c↓1c↓0 + c↓1c↓0)x + c↓0↑2\bigrp\,\mod u(x),$$
where $x↑{2n-2}$, $\ldotss$, $x↑n$ can be replaced
by polynomials in the auxiliary table. The net time to compute
$x↑p\mod u(x)$ comes to $O\biglp n↑2(\log p)↑3\bigrp$ units,
and we obtain the second row of $Q$. To get further rows of $Q$,
we form $x↑{2p}\mod u(x)$, $x↑{3p}\mod u(x)$, $\ldots$ simply
by multiplying repeatedly by $x↑p\mod u(x)$, in a fashion
analogous to squaring mod $u(x)$; step B2 is completed in $O\biglp
n↑2(\log p)↑3 + n↑3(\log p)↑2\bigrp$ units of time. The same
upper bound applies to steps B1, B2, and B3 taken as a whole;
these three steps tell us the number of factors of $u(x)$.

But when $p$ is large and we get to step B4, we
are asked to calculate a greatest common divisor for $p$ different
values of $s$, and that is out of the question if $p$ is very
large. This hurdle was surmounted by Hans Zassenhaus [{\sl J.
Number Theory \bf 1} (1969), 291--311], who showed how to determine
all the ``useful'' values of $s$. Let $v(x)$ be a solution to (8), and let $w(x) =
\prod(x - s)$ where the product is over all $0 ≤ s < p$ such
that $\gcd\biglp u(x),\,v(x) - s\bigrp ≠ 1$. By (14), this quantity $w(x)$
is the polynomial of least degree such that $u(x)$ divides $w\biglp v(x)\bigrp$.
Algorithm N can therefore be adapted to find the coefficients
of $w$: Let $A$ be the $(r + 1) \times n$ matrix whose $k$th
row contains the coefficients of $v(x)↑k \mod
u(x)$, for $0 ≤ k ≤ r$. Apply the method of Algorithm N until
the first dependence is found in step N3; then the algorithm
terminates with $w(x) = v↓0 + v↓1x +\cdots + v↓kx↑k$,
where $v↓j$ is defined in (18).\xskip (An example is worked out below.)\xskip
At this point $2 ≤ k ≤ r$; in rare circumstances we may have
$k = n$.

It remains to find the factors of $w(x)$ modulo
a large prime $p$, when $w$ is known to split into linear factors.
Suppose $w(x) = (x -s↓1) \ldotsm (x - s↓k)$; then it divides
$x(x - 1) \ldotsm (x - p + 1) = x↑p - x = x(x↑{(p-1)/2} - 1)(x↑{(p-1)/2}
+ 1)$, hence the identity
$$w(x) = \gcd\biglp w(x),\, x + t) \cdot\gcd\biglp w(x),\,(x
+ t)↑{(p-1)/2} - 1) \cdot \gcd\biglp w(x),\,(x +
t)↑{(p-1)/2} + 1)\eqno (20)$$
holds for all integers $t$. Zassenhaus's procedure
for factoring $w$ is to try computing $\gcd\biglp w(x),\,(x+t)↑{(p-1)/2}-1\bigrp$ 
for $t = 0$, 1, 2, $\ldots$ until
$w$ has been completely split. At first glance this may appear
to be an inefficient trial-and-error method, but actually it
finds the factors very rapidly, since the probability of a nontrivial
gcd in (20) is approximately $1 - 2↑{-k}$ when $t$ is chosen
at random. The reason is that $x - s↓i$ divides $(x + t)↑{(p-1)/2}-1$
if and only if $(s↓i + t)↑{(p-1)/2}\mod p = 1$, and this
occurs for about half of all values $t$.\xskip(Exercise 14 gives a rigorous
proof that $\gcd\biglp w(x),(x+t)↑{(p-1)/2}-1\bigrp$ will be nontrivial more than
${1\over2}+O(p↑{-1})$ of the time when $t$ is chosen at random. Therefore the
expected number of trials is roughly 2, and we ``never'' will have to wait long.)
 
For example, let's reconsider the polynomial $v↑{[3]}(x)
= x↑7 + 12x↑5 + 10x↑4 + 9x↑3 + 11x↑2 + 9x$ mentioned earlier,
and let's pretend that 13 is a large prime. Then
\def\circle#1{\hjust to 10pt{#1\hskip-10ptminus10pt
\raise 6.944pt\hjust{\:@\char'141}\hskip0ptminus10pt}}
$$\hjust to size{$\dispstyle{\hjust{Matrix $A$}\lower5pt\null\atop
\left(\,\vcenter{\halign{\hjust to 10pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\!
\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\!
\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}\cr
1⊗0⊗0⊗0⊗0⊗0⊗0⊗0\cr
0⊗9⊗11⊗9⊗10⊗12⊗0⊗1\cr
4⊗4⊗6⊗9⊗1⊗7⊗12⊗1\cr
4⊗6⊗3⊗6⊗11⊗8⊗0⊗5\cr
}}\,\right)}\hfill
{\hjust{is transformed into}\lower5pt\null\atop
\left(\,\vcenter{\halign{\hjust to 10pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\!
\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\!
\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}⊗\hjust to 20pt{\hfill#}\cr
\circle{12}⊗0⊗0⊗0⊗0⊗0⊗0⊗0\cr
0⊗0⊗0⊗0⊗0⊗\circle{12}⊗0⊗0\cr
0⊗0⊗0⊗0⊗0⊗0⊗\circle{12}⊗0\cr
9⊗0⊗0⊗0⊗0⊗8⊗0⊗0\cr
}}\,\right)}$}$$
so we have $w(x) = 9 + 8x + x↑3$. Setting $t =
0$ in (20) produces the factor $x + 1 = x - 12$, and we replace
$w(x)$ by $w(x)/(x - 12) = x↑2 + 12x + 9$. When $t = 1$ we get
the other factors
$x - 6$ and $x - 8$. The useful values of $s$ with respect to
$v↑{[3]}(x)$ are 6, 8, and 12.

If we assume (as we may) that a nontrivial factor of $w(x)$
will be found after $O(1)$ applications of (20), we can give an upper
bound on the time to perform B4: It takes $O\biglp r↑2n↑2(\log p)↑2\bigrp$
steps to compute each $w↓j(x)$ from $v↑{[j]}(x)$, plus at most
$O\biglp r↑3(\log p)↑3+r↑4(\log p)↑2\bigrp$ steps to find their roots,
plus at most $O(rn↑3(\log p)↑2\bigrp$ steps to compute gcd's as in (14).
The computation will usually be completed even faster, and $r$ is usually
small compared to $n$. Thus, step B4 is not the bottleneck after all,
when we use Zassenhaus's suggestions.

For discussion, see E. R. Berlekamp, {\sl Math.\ Comp.\ \bf24} (1970), 713--735;
Robert T. Moenck, {\sl Math.\ Comp.\ \bf31} (1977), 235--250.

\subsectionbegin{Distinct degree factorization} A
somewhat simpler method that often obtains factors modulo $p$
can be based on the fact that an irreducible polynomial $q(x)$
of degree $d$ is a divisor of $x↑{p↑d}- x$, and it is
not a divisor of $x↑{p↑c} - x$ for $c < d$; see exercise
16. We proceed as follows:

\yskip\hang\textindent{\bf S1.}Rule
out squared factors and find the matrix $Q$, as in Berlekamp's
method. Also set $v(x) ← u(x)$, $w(x) ← \hjust{``$x$''}$, and $d ← 0$.\xskip (Here
$v(x)$ and $w(x)$ are variables that have polynomials as values.)

\yskip\hang\textindent{\bf S2.}Increase $d$ by 1 and replace $w(x)$ by $w(x)↑p
\mod u(x)$.\xskip $\biglp$In other words, the coefficients $(w↓0, \ldotss
, w↓{n-1})$ are replaced by $(w↓0, \ldotss , w↓{n-1})Q$. At this
point $w(x) = x↑{p↑d}\mod u(x)$.$\bigrp$

\yskip\hang\textindent{\bf S3.}Find $g(x) = \gcd\biglp w(x)-x,v(x)\bigrp$.\xskip
$\biglp$This is the product of all the irreducible factors of $u(x)$
whose degree is $d$.$\bigrp$\xskip Replace $v(x)$ by $v(x)/g(x)$.

\yskip\hang\textindent{\bf S4.}If $d < {1\over 2}\hjust{deg}(v)$, return to S2.
Otherwise $v(x)$ is irreducible, and the procedure terminates.\quad\blackslug
%folio 550 galley 13 (C) Addison-Wesley 1978	*
\yyskip This procedure determines the product of
all irreducible factors of each degree $d$, and therefore it
tells us how many factors there are of each degree. Since the
three factors of our example polynomial (19) have different
degrees, they would all be discovered. The total running time,
analyzed as above, is $O\biglp n↑3(\log p)↑2 + n↑2(\log p)↑3\bigrp$.

The distinct degree factorization technique was
known to several people in 1960 [cf.\ S. W. Golomb, L. R. Welch,
A. Hales, ``On the factorization of trinomials over GF(2),''
Jet Propulsion Laboratory memo 20--189 (July 14, 1959)], but
there seem to be no references to it in the ``open literature.''
Previous work by \v S. Schwarz, {\sl Quart.\ J. Math.}, Oxford (2)
{\bf 7} (1956), 110--124, had shown how to determine the number
of irreducible factors of each degree, but not their product,
using the matrix $Q$.

If the distinct degree factorization procedure doesn't find a complete
factorization, it is not necessary to abandon hope: There is still a good
chance that the factors can be found by computing $\gcd\biglp g(x),\,
(x+t)↑{(p↑d-1)/2}-1\bigrp$ for $t=0$, 1, $\ldotss$, $p-1$, when $p$ is
odd and all irreducible factors of $g(x)$ have degree $d$. Every divisor of
$x↑{p↑d}-x$ also divides $$(x+t)↑{p↑d}-(x+t)=(x+t)\biglp(x+t)↑{(p↑d-1)/2}-1\bigrp
\biglp(x+t)↑{(p↑d-1)/2}+1\bigrp,$$so we can argue as in (20). If $d=1$, all
the linear factors will be found quickly, even when $p$ is large. If $d>1$,
we might not split $g(x)$ completely, but the prospects are good, {\sl especially}
if $p$ is large.

For example, there are eight irreducible polynomials $f(x)$ of degree 3, modulo
3, and they will all be distinguished by calculating $\gcd\biglp f(x),\,
(x+t)↑{13}-1\bigrp$ for $0≤t<3$:
$$\vjust{\halign{$\hfill#\null$⊗$\hfill#\null$⊗$\hfill#$\qquad⊗$\ctr{#}$⊗\qquad
$\ctr{#}$⊗\qquad$\ctr{#}$\cr
⊗f(x)⊗⊗t=0⊗t=1⊗t=2\cr
\noalign{\vskip4pt}
x↑3+⊗⊗2x+1⊗1⊗1⊗1\cr
x↑3+⊗⊗2x+2⊗f(x)⊗f(x)⊗f(x)\cr
x↑3+⊗x↑2+⊗2⊗f(x)⊗f(x)⊗1\cr
x↑3+⊗x↑2+⊗x+2⊗f(x)⊗1⊗f(x)\cr
x↑3+⊗x↑2+⊗2x+1⊗1⊗f(x)⊗f(x)\cr
x↑3+⊗2x↑2+⊗1⊗1⊗f(x)⊗1\cr
x↑3+⊗2x↑2+⊗x+1⊗1⊗1⊗f(x)\cr
x↑3+⊗2x↑2+⊗2x+x⊗f(x)⊗1⊗1\cr}}$$
On the other hand, when the number of irreducible polynomials of degree $d$
exceeds\-\ $2↑p$, it is clear that there will exist irreducibles that cannot
be distinguished by this method.\xskip M. O. Rabin has shown how to extend
the distinct-degree factorization technique to a complete factorization in
all cases, by doing arithmetic in a field with $p↑n$ elements (see exercise
31).

\subsectionbegin{Factoring over the integers} It
is somewhat more difficult to find the complete factorization
of polynomials with integer coefficients when we are {\sl not}
working modulo $p$, but some reasonably efficient methods are
available for this purpose.

Isaac Newton gave a method for finding linear and
quadratic factors of polynomials with integer coefficients in
his {\sl Arithmetica Universalis\/} (1707). This method was extended
by an astronomer named Friedrich von Schubert in 1793, who showed
how to find all factors of degree $n$ in a finite number of
steps; see M. Cantor, {\sl Geschichte der Mathematik \bf 4}
(Leipzig: Teubner, 1908), 136--137.\xskip L. Kronecker rediscovered
von Schubert's method independently about 90 years later; but
unfortunately the method is very inefficient when $n$ is five
or more. Much better results can be obtained with the help of
the ``mod $p$'' factorization methods presented above.

Suppose that we want to find the irreducible factors
of a given polynomial
$$u(x) = u↓nx↑n + u↓{n-1}x↑{n-1} +\cdots + u↓0,\qquad u↓n ≠ 0,$$
over the integers. As a first step, we can divide
by the greatest common divisor of the coefficients, and this
leaves us with a {\sl primitive} polynomial. We may also assume
that $u(x)$ is squarefree, by dividing out $\gcd\biglp u(x),
u↑\prime (x)\bigrp$ as above.

Now if $u(x) = v(x)w(x)$, where all of these polynomials
have integer coef\-ficients, we obviously have $u(x) ≡ v(x)w(x)
\modulo p$ for all primes $p$, so there is a nontrivial factorization
modulo $p$ unless $p$ divides $\lscr(u)$. Berlekamp's efficient
algorithm for factoring $u(x)$ modulo $p$ can therefore be used
in an attempt to reconstruct possible factorizations of $u(x)$
over the integers.

For example, let
$$u(x) = x↑8 + x↑6 - 3x↑4 - 3x↑3 + 8x↑2 + 2x - 5.\eqno (21)$$
We have seen above in (19) that
$$u(x) ≡ (x↑4 + 2x↑3 + 3x↑2 + 4x + 6)(x↑3
+ 8x↑2 + 4x + 12)(x + 3)\modulo{13};\eqno(22)$$
and the complete factorization of $u(x)$ modulo 2 shows
one factor of degree 6 and another of degree 2 (see exercise
10). From (22) we can see that $u(x)$ has no factor of degree
2, so it must be irreducible over the integers.

This particular example was perhaps too simple;
experience shows that most irreducible polynomials can be recognized
as such by examining their factors modulo a few primes, but
it is {\sl not\/} always so easy to establish irreducibility. For example,
there are polynomials that 
can be properly factored modulo $p$ for all primes
$p$, with consistent degrees of the factors, yet they are irreducible
over the integers (see exercise 12).

Almost all polynomials are irreducible over the
integers, as shown in exercise 27. But we usually aren't trying
to factor a random polynomial; there is probably some reason
to expect a nontrivial factor or else the calculation would
not have been attempted in the first place. We need a method
that identifies factors when they are there.

In general if we try to find the factors of $u(x)$
by considering its behavior modulo different primes, the results will not be
easy to combine; for example, if $u(x)$
actually is the product of four quadratic polynomials, it will
be hard to match up their images with respect to different prime
moduli. Therefore it is desirable to stick to a single prime and
to see how much mileage we can get out of it, once we feel that the
factors modulo this prime have the right degrees.

One idea is to work modulo a very {\sl large} prime
$p$, big enough so that the coefficients in any true factorization
$u(x) = v(x)w(x)$ over the integers must actually lie between
$-p/2$ and $p/2$. Then all possible integer factors can be ``read
off'' from the mod $p$ factors we know how to compute.

Exercise 20 shows how to obtain fairly good bounds
on the coefficients of polynomial factors. For example, if (21)
were reducible it would have a factor $v(x)$ of degree $≤4$, and
the coefficients of $v$ would be at most 67 in magnitude by
the results of that exercise. So all potential factors of $u(x)$
will be fairly evident if we work modulo any prime $p > 134$.
Indeed, the complete factorization modulo 137 is
$$(x↑3 + 32x↑2 + 21x + 56)(x↑5 - 32x↑4 + 45x↑3 - 2x↑2 - 51x - 27),$$
and we see immediately that $x↑3 +\cdots
+ 56$ is not a factor since 56 doesn't divide 5.\xskip $\biglp$Incidentally,
it is not trivial to obtain good bounds on the coefficients
of polynomial factors, since a lot of cancellation can occur
when polynomials are multiplied. For example, the innocuous-looking
polynomial $x↑n - 1$ has irreducible factors whose coefficients
exceed $\exp(n↑{1/\!\lg\lg n})$ for infinitely many $n$.\xskip
[See R. C. Vaughan, {\sl Michigan Math.\ J. \bf 21} (1974), 289--295].\xskip
The factorization of $x↑n-1$ is discussed in exercise 32.$\bigrp$

Instead of using a large prime $p$, which might
have to be truly enormous if $u(x)$ has large degree or large
coefficients, we can also make use of small $p$, provided that
$u(x)$ is squarefree mod $p$. For in this case, an important
construction introduced by K. Hensel [{\sl Theorie der Algebraischen
Zahlen} (Leipzig: Teubner, 1908), Chapter 4] can be used to
extend a factorization modulo $p$ in a unique way to a factorization
modulo $p↑e$ for arbitrarily high $e$. Hensel's method is described
in exercise 22; if we apply it to (22) with $p = 13$ and $e
= 2$, we obtain the unique factorization $u(x) ≡ (x - 36)(x↑3
- 18x↑2 + 82x - 66)(x↑4 + 54x↑3 - 10x↑2 + 69x + 84) \modulo
{169} = v↓1(x)v↓3(x)v↓4(x)$, say. Clearly $v↓1(x)$ and $v↓3(x)$
are not factors of $u(x)$ over the integers; and neither is
their product $v↓1(x)v↓3(x)$ when the coefficients have been
reduced modulo 169 to the range $(-{169\over 2},{169\over
2})$. Thus we have exhausted all possibilities, proving once
again that $u(x)$ is irreducible over the integers---this time
using only its factorization modulo 13.

The example we have been considering is atypical
in one important respect: We have been factoring the {\sl monic}
polynomial $u(x)$ in (21), so we could assume that all its factors
were monic. What should we do if $u↓n > 1$? In such a case,
the leading coefficients of all but one of the polynomial factors
can be varied almost arbitrarily modulo $p↑e$; we certainly
don't want to try all possibilities. Perhaps the reader has
already noticed this problem. Fortunately there is a simple way
out: the factorization $u(x) = v(x)w(x)$ implies a factorization
$u↓nu(x) = v↓1(x)w↓1(x)$ where $\lscr(v↓1) = \lscr(w↓1) = u↓n =
\lscr(u)$.\xskip (``Do you mind if I multiply your polynomial by its
leading coefficient before factoring it?'')\xskip We can proceed essentially
as above, but using $p↑e ≥ 2B$ where $B$ now bounds the maximum
coefficient for factors of $u↓nu(x)$ instead of $u(x)$.

Putting these observations all together results in the following procedure:

\yskip\hang\textindent{\bf F1.}Find the unique factorization
$u(x) ≡ \lscr(u)v↓1(x)\ldotsm v↓r(x)\modulo {p↑e}$, where $p↑e$ is sufficiently
large as explained above, and where
the $v↓j(x)$ are monic.\xskip (This will be possible for all but a
few primes $p$, see exercise 23.)\xskip Set $d ← 1$.

\yskip\hang\textindent{\bf F2.}For every combination of factors $v(x) = v↓{i↓1}
(x) \ldotsm v↓{i↓d}(x)$, with $i↓1
= 1$ if $d = {1\over 2}r$, form the unique polynomial
$\=v(x) ≡ \lscr(u)v(x)\modulo {p↑e}$ whose coefficients all lie
in the interval $[-{1\over 2}p↑e, {1\over 2}p↑e)$. If $v(x)$
divides $\lscr(u)u(x)$, output the factor pp$\biglp v(x)\bigrp
$, divide $u(x)$ by this factor, and remove the corresponding
$v↓i(x)$ from the list of factors modulo $p↑e$; decrease $r$ by the number of
factors removed, and terminate the algorithm if $d>{1\over2}r$.

\yskip\hang\textindent{\bf F3.}Increase $d$ by 1, and return to F2 if $d > {1\over
2}r$.\quad\blackslug

\yyskip\noindent At the conclusion of this process, the current value of
$u(x)$ will be the final irreducible factor of the originally
given polynomial. Note that if $|u↓0| < |u↓n|$, it is preferable
to do all of the work with the reverse polynomial $u↓0x↑n +\cdots
+ u↓n$, whose factors are the reverses of the factors of $u(x)$.

The above algorithm contains an obvious bottleneck:
We may have to test as many as $2↑{r-1}$ potential factors $v(x)$.
The average value of $2↑r$ in a random situation is about $n$,
or perhaps $n↑{1.5}$ (see exercise 5), but in nonrandom situations
we will want to speed up this part of the routine as much as
we can. One way to rule out spurious factors quickly is to compute
the trailing coefficient $\=v(0)$ first, continuing only if this
divides $\lscr(u)u(0)$.

Another important way to speed up the procedure
is to reduce $r$ so that it tends to reflect the true number
of factors. The distinct degree factorization algorithm above
can be applied for various small primes $p↓j$, thus obtaining
for each prime a set $D↓j$ of possible degrees of factors modulo
$p↓j$; see exercise 26. We can represent $D↓j$ as a string of
$n$ binary bits. Now we compute the intersection $\union D↓j$, namely
the logical ``and'' of these bit strings, and we perform step
F2 only for $d \in \union D↓j$. Furthermore $p$ is selected as that
$p↓j$ having the smallest value of\penalty999\ $r$. This technique is due
to David R. Musser, whose experience suggests trying about five
primes $p↓j$ (see {\sl JACM \bf 25} (1978), 271--282).
 Of course we would stop immediately if the current
$\union D↓j$ shows that $u(x)$ is irreducible.

 Musser has given a
complete discussion of a factorization method similar to the steps above, in
{\sl JACM \bf 22} (1975), 291--308. The procedure above incorporates an
improvement suggested in 1978 by G. E. Collins, namely to look for trial divisors
by taking combinations of $d$ factors at a time rather than combinations of total
degree $d$. This improvement is important because of the statistical
behavior of the modulo-$p$ factors of polynomials that are irreducible
over the rationals (cf.\ exercise 33). 
%folio 558 galley 14 (C) Addison-Wesley 1978	*
\subsectionbegin{Greatest common divisors} Similar techniques
can be used to calculate greatest common divisors of polynomials:
If $\gcd\biglp u(x), v(x)\bigrp = d(x)$ over the integers, and
if $\gcd\biglp u(x), v(x)\bigrp = q(x)\modulo p$ where $q(x)$
is monic, then $d(x)$ is a common divisor of $u(x)$ and $v(x)$
modulo $p$; hence
$$d(x)\quad\hjust{divides}\quad q(x)\quad\modulo p.\eqno(23)$$
If $p$ does not divide the leading coefficients
of both $u$ and $v$, it does not divide the leading coefficient
of $d$; in such a case $\hjust{deg}(d) ≤\hjust{deg}(q)$. When $q(x) = 1$
for such a prime $p$, we must therefore have deg$(d) = 0$, and
$d(x) =\gcd\biglp\hjust{cont}(u), \hjust{cont}(v)\bigrp $. This justifies
the remark made in Section 4.6.1 that the simple computation
of $\gcd\biglp u(x), v(x)\bigrp$ modulo 13 in 4.6.1--6 is enough
to prove that $u(x)$ and $v(x)$ are relatively prime over the
integers; the comparatively laborious calculations of Algorithm
4.6.1E or Algorithm 4.6.1C are unnecessary. Since two random
primitive polynomials are almost always relatively prime over
the integers, and since they are relatively prime modulo $p$
with probability $1 - 1/p$, it is usually a good idea to do
the computations modulo $p$.

As remarked above, we need good methods also for
the nonrandom polynomials that arise in practice. Therefore we wish to
sharpen our techniques and discover how to find $\gcd\biglp u(x),v(x)\bigrp$
in general, over the integers, based entirely on information that we obtain
working modulo primes $p$. We may assume that $u(x)$ and $v(x)$ are
primitive.

Instead of calculating $\gcd\biglp u(x), v(x)\bigrp$ directly, it will
be convenient to search instead for the polynomial
$$\=d(x) = c \cdot\gcd\biglp u(x), v(x)\bigrp ,\eqno(24)$$
where the constant $c$ is chosen so that
$$\lscr(\=d) =\gcd\biglp\lscr(u),\lscr(v)\bigrp .\eqno(25)$$
This condition will always hold for suitable $c$,
since the leading coefficient of any common divisor of $u(x)$
and $v(x)$ must be a divisor of $\gcd\biglp \lscr(u), \lscr(v)\bigrp
$. Once $\=d(x)$ has been found satisfying these conditions,
we can readily compute pp$\biglp \=d(x)\bigrp $, which is
the true greatest common divisor of $u(x)$ and $v(x)$. Condition
(25) is convenient since it avoids the uncertainty of unit multiples
of the gcd; it is essentially the idea we used to control leading
coefficients in our factorization routine.

If $p$ is a sufficiently large prime, based on
the bounds for coefficients in exercise 20 applied either to
$\lscr(\=d)u(x)$ or $\lscr(\=d)v(x)$, let us compute
the unique polynomial $\=q(x) ≡ \lscr(\=d)q(x)\modulo
p$ having all coefficients in $[-{1\over 2}p, {1\over 2}p)$.
When pp$\biglp \=q(x)\bigrp$ divides both $u(x)$ and $v(x)$,
it must equal $\gcd\biglp u(x), v(x)\bigrp$ because of (23).
On the other hand if it does not divide both $u(x)$ and $v(x)$
we must have deg$(q) >\hjust{deg}(d)$. A study of Algorithm 4.6.1E
reveals that this will be the case only if $p$ divides the leading
coefficient of one of the nonzero remainders computed by that
algorithm with exact integer arithmetic; otherwise Euclid's
algorithm modulo $p$ deals with precisely the same sequence
of polynomials as Algorithm 4.6.1E except for nonzero constant
multiples (modulo $p$). So only a small number of ``unlucky''
primes can cause us to miss the gcd, and we will soon find it
if we keep trying.

If the bound on coefficients is so large that single-precision
primes $p$ are insufficient, we can compute $\=d(x)$
modulo several primes $p$ until it has been determined via the
Chinese remainder algorithm in Section 4.3.2. This approach,
which is due to W. S. Brown and G. E. Collins, has been described
in detail by Brown in {\sl JACM \bf 18} (1971), 478--504. Alternatively,
as suggested by J. Moses and D. Y. Y. Yun [{\sl Proc.\ ACM Conf.\
\bf 28} (1973), 159--166], we can use Hensel's method to determine
$\=d(x)$ modulo $p↑e$ for sufficiently large $e$. Hensel's
construction is valid directly only when
$$\gcd\biglp d(x),\,u(x)/d(x)\bigrp = 1\qquad\hjust{or}\qquad\gcd\biglp
d(x),\,v(x)/d(x)\bigrp = 1,\eqno (26)$$
since the idea is to apply the techniques of exercise
22 to one of the factorizations $\lscr(\=d)u(x) ≡ \=q(x)
u↓1(x)$ or $\lscr(\=d)v(x) ≡ \=q(x)v↓1(x)\modulo
p$. In the comparatively rare cases when (26) fails, we can
still find the gcd by casting out squared factors in an appropriate
manner, as shown in exercise 29. The complete procedure has
been discussed by Miola and Yun in {\sl SIGSAM Bulletin \bf 8},
3 (August 1974), 46--54; it appears to be computationally superior
to the Chinese remainder approach.

The gcd algorithms sketched here are significantly
faster than those of Section 4.6.1 except when the polynomial
remainder sequence is very short. Perhaps the best combined
approach would be to start with the computation of $\gcd\biglp
u(x), v(x)\bigrp$ modulo a fairly small prime $p$, not a divisor
of both $\lscr(u)$ and $\lscr(v)$. If the result $q(x)$ is 1, we're
done; if it has high degree, we use Algorithm 4.6.1C\null; otherwise
we use one of the above methods, first computing a bound for
the coefficients of $\=d(x)$ based on the coefficients
of $u(x), v(x)$, and the (small) degree of $q(x)$. As in the
factorization problem, we should apply this procedure to the
reverses of $u(x), v(x)$ and reverse the result, if the trailing
coefficients are simpler than the leading ones.

\subsectionbegin{Multivariate polynomials} Similar
techniques lead to useful algorithms for factorization or gcd
calculations on multivariate polynomials with integer coefficients.
Such a polynomial $u(x↓1, \ldotss , x↓t)$ can be dealt with modulo
the irreducible polynomials $x↓2 - a↓2$, $\ldotss$, $x↓t - a↓t$,
yielding the univariate polynomial $u(x↓1, a↓2, \ldotss , a↓t)$;
these irreducible polynomials play the role of $p$
in the above discussion.\xskip $\biglp$Note that $v(x)\mod (x - a)$ is
$v(a)$.$\bigrp$\xskip When the integers $a↓2$, $\ldotss$,
$a↓t$ have been chosen so that $u(x↓1, a↓2, \ldotss , a↓t)$ has
the same degree in $x↓1$ as $u(x↓1, x↓2, \ldotss , x↓t)$, an
appropriate generalization of Hensel's construction will ``lift'' squarefree
factorizations of this univariate polynomial to factorizations
modulo $(x↓2 - a↓2)↑{n↓2}$, $\ldotss$, $(x↓t - a↓t)↑{n↓t}$,
where $n↓j$ is the degree of $x↓j$ in $u$; at the same time
we can work also modulo an appropriate integer prime $p$. As many
as possible of the $a↓j$ should be zero, so that sparseness
of the intermediate results is retained. For details, see P.
S. Wang and L. P. Rothschild, {\sl Math.\ Comp.\ \bf 29} (1975),
935--950, in addition to the papers by Musser and by Moses and
Yun cited earlier.

\exbegin{EXERCISES}

\trexno 1. [M24] Let $p$ be prime.
What is the probability that a random polynomial of degree\penalty999\ $n$
has a linear factor (a factor of degree 1), when $n ≥ p$?\xskip (Assume
that each of the $p↑n$ monic polynomials modulo $p$ is equally
probable.)

\trexno 2. [M25] (a) Show that any monic polynomial $u(x)$, over
a unique factorization domain, may be expressed uniquely in
the form
$$u(x) = v(x)↑2w(x),$$
where $w(x)$ is squarefree $\biglp$has no factor of positive
degree of the form $d(x)↑2\bigrp$ and both $v(x)$ and $w(x)$
are monic.\xskip(b) (E. R. Berlekamp.)\xskip How many monic
polynomials of degree $n$ are squarefree modulo $p$, when $p$
is prime?

\exno 3. [M25] Let $u↓1(x)$, $\ldotss$, $u↓r(x)$ be polynomials
over a field $S$, with $u↓j(x)$ relatively prime to $u↓k(x)$
for all $j ≠ k$. For any given polynomials $w↓1(x)$, $\ldotss$,
$w↓r(x)$ over $S$, prove that there is a unique polynomial $v(x)$
over $S$ such that
$$\def\\{\hjust{deg}}
\\(v)<\\(u↓1)+\cdots+\\(u↓r)$$
and
$$v(x) ≡ w↓j(x)\quad \biglp\hjust{modulo }u↓j(x)\bigrp$$
for $1 ≤j≤r$.\xskip (Compare with Theorem 4.3.2C.)

\exno 4. [HM28] Let $a↓{np}$ be the number of monic irreducible
polynomials of degree $n$, modulo a prime $p$. Find a formula
for the generating function $G↓p(z) = \sum ↓n a↓{np}z↑n$.\xskip [{\sl Hint:}
Prove the following identity connecting power series: $f(z)
= \sum ↓{j≥1}g(z↑j)/j↑t$ if and only if
$g(z)=\sum↓{n≥1} \mu (n)f(z↑n)/n↑t$.]\xskip What is $\lim↓{p→∞}a↓{np}/p↑n$?

\exno 5. [HM30] Let $A↓{np}$ be the average number of factors
of a randomly selected polynomial of degree $n$, modulo a prime
$p$. Show that
$\lim↓{p→∞} A↓{np} = H↓n$.\xskip What is the limiting average value of $2↑r$,
when there are $r$ factors?

\exno 6. [M21] (J. L. Lagrange, 1771.)\xskip Prove the congruence
(9).\xskip [{\sl Hint:} Factor $x↑p - x$ in the field of $p$
elements.]

\exno 7. [M22] Prove Eq.\ (14).

\exno 8. [HM20] How can we be sure that the vectors output by
Algorithm N are linearly independent?

\exno 9. [20] Explain how to construct a table of reciprocals
mod 101 in a simple way, given that 2 is a primitive root of
101.

\trexno 10. [21] Find the complete factorization of the polynomial
$u(x)$ in (21), modulo 2, using Berlekamp's procedure.

\exno 11. [22] Find the complete factorization of the polynomial
$u(x)$ in (21), modulo 5.

\trexno 12. [M22] Use Berlekamp's algorithm to determine the number
of factors of $u(x) = x↑4 + 1$ modulo $p$, for all primes
$p$.\xskip [{\sl Hint:} Consider the cases $p = 2$, $p = 8k + 1$, $p =
8k + 3$, $p = 8k + 5$, $p = 8k + 7$ separately; what is the matrix
$Q$? You need not discover the factors; just determine how many
there are.]

\exno 13. [M25] Give an explicit formula for the factors of
$x↑4 + 1$, modulo $p$, for all odd primes $p$, in terms of the quantities
$\sqrt{-1}$, $\sqrt2$, $\sqrt{-2}$ (if such quantities exist modulo
$p$).

\exno 14. [M30] (M. O. Rabin.)\xskip Let $w(x)=(x-s↓1)\ldotsm(x-s↓k)$ where
$0≤s↓1<\cdots<s↓k<p$, $k≥2$, and $p$ is prime. Let $P(s↓1,\ldotss,s↓k)$ be 
the probability
that $\gcd\biglp w(x),\,(x+t)↑{(p-1)/2}-1\bigrp$ is neither 1 nor $w(x)$,
when $t$ is an integer selected at random, modulo $p$. Prove that
$P(s↓1,\ldotss,s↓k)≥1/2-1/(2p)$.

\trexno 15. [M27] Design an algorithm to calculate the ``square
root'' of a given integer $u$ modulo a given prime $p$, i.e.,
to find an integer $U$ such that $U↑2 ≡ u\modulo p$ whenever
such a $U$ exists. Your algorithm should be efficient even for
very large primes $p$.\xskip (A solution to this problem leads to
a procedure for solving any given quadratic equation modulo\penalty999\ $p$, using
the quadratic formula in the usual way.)

\exno 16. [M30] Given that $f(x)$ is an irreducible polynomial
modulo a prime $p$, of degree $n$, prove that the $p↑n$ polynomials
of degree less than $n$ form a field under arithmetic modulo
$f(x)$ and $p$.\xskip ({\sl Note:} The existence of irreducible polynomials
of each degree is proved in exercise 4; therefore fields with
$p↑n$ elements exist for all primes $p$ and all $n ≥ 1$.)\xskip
(b) Show that any field with $p↑n$ elements has a ``primitive root'' element
$\xi$ such that the elements of the field are $\{0,1,\xi,\xi↑2,\ldotss,
\xi↑{p↑n-2}\}$.\xskip[{\sl Hint:} Exercise 3.2.1.2-16 proves this when
$n=1$.]\xskip(c) If $f(x)$ is an irreducible polynomial modulo $p$, of
degree $n$, prove that $x↑{p↑m}-x$ is divisible by $f(x)$ if and only if
$m$ is a multiple of $n$.\xskip$\biglp$It follows that we can test
irreducibility rather quickly: A given $n$th degree polynomial $f(x)$ is
irreducible modulo $p$ if and only if $x↑{p↑n}-x$ is divisible by $f(x)$
and $\gcd\biglp x↑{p↑{n/q}}-x,\,f(x)\bigrp = 1$ for all primes $q$ dividing $n
$.$\bigrp$